std::equal_range可能的实现

std::equal_range possible implementation

提问人:Damir Tenishev 提问时间:11/11/2023 最后编辑:Damir Tenishev 更新时间:11/11/2023 访问量:59

问:

std::equal_range 显示了以下可能的实现:std::equal_range

template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}

是否有特定的原因可以重新开始而不是使用 的结果?firststd::upper_boundstd::lower_bound

例如:

template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt lower = std::lower_bound(first, last, value);
    return std::make_pair(lower, std::upper_bound(lower, last, value));
}

在我看来,再次检查范围 [首先,更低]似乎太过分了,因为无论如何都应该在另一部分。upper

我知道 en.cppreference.com 提供了最简单的示例来解释算法背后的想法,而不是可能很复杂的优化版本。我的问题不同。我可以使用我的优化还是错过了一些拐角点?比如“考虑你的实现会在空数组上做什么,或者如果范围缺失,等等”。

我是否遗漏了什么,这种简单的优化可能会有风险?

我不是在尝试实现最佳性能(就像在 libstdc++ 实现中一样), 我只是好奇这个简单的优化是否安全。

C++ STL

评论

4赞 Jerry Coffin 11/11/2023
我相信它应该是安全的,是的。
1赞 Red.Wave 11/11/2023
cppreference 刚刚提供了一个衬里。在现代 C++ 中,您甚至不需要:只需要一对大括号:make_pairreturn {lower,whatever};
0赞 Damir Tenishev 11/11/2023
@Red.Wave,谢谢我知道并在我的代码中使用它。我只是使用了 cppreference 的原始代码,并尽最大努力更改尽可能少的代码以保持想法可见。正如我在问题中强调的那样,我担心的不是想象中的cppreferences代码的“低效率”,而只是我的更改的正确性。我不确定我是否错过了这个变化。某种极端情况。这个问题是由更复杂的代码段引起的,我被迫做这样的技巧并且不能使用 std::equal_range。

答: 暂无答案