c++ - std::equal_range 的可能实现

Question

std::equal_range关于 cppreference.com 的文档显示了一个可能的实现:

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));
}

但这看起来更优化，同时仍然非常简单:

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

由于此解决方案非常明显，是否有任何理由未使用它？

Answer 1

cppreference 上给出的实现是可能的实现，不一定是最优化的实现。我认为为了清楚起见，将其包括在内是为了让读者可以更好地了解算法在内部做什么，而不是作为所有可能实现中最快的指南。

只要您正在优化实现，您可能会考虑使用一些逻辑来检查范围是否较小，如果是，则使用线性搜索而不是二分搜索。

查看实际实现以了解其结构可能会有所帮助。看看，比方说，the libstdc++ implementation ，与 cppreference 上给出的更清晰但效率较低的版本相比，它异常密集且更难阅读。该版本 - 截至撰写本文时 - 使用完全不同的方法:

1. 使用初始二分搜索来搜索元素的任何拷贝。
2. 对剩余窗口使用二次二分搜索来查找该范围内元素的第一个和最后一个拷贝。

这种方法可能比您提议的方法更快，因为可以共享两个二进制搜索的大量工作。