可能实现std :: equal_range

Question

cppreference.com上的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));
}

但这看起来更优,同时还很简单:

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上给出的实现是一种可能的实现,不一定是最优化的实现.我认为它是为了清晰起见而包含的,以便读者可以更好地了解算法在内部执行的操作,而不是作为所有可能实现中最快的指南.

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

查看实际实现以了解它的结构可能会有所帮助.比如说libstdc ++实现,它比cppreference给出的更清晰但效率更低的版本更加密集且难以阅读.该版本 - 截至撰写本文时 - 使用了一种完全不同的方法:

1. 使用初始二进制搜索来搜索元素的任何副本.
2. 在剩余窗口上使用辅助二进制搜索,以查找该范围内元素的第一个和最后一个副本.

这种方法可能比你提出的方法更快,因为可以共享来自两个二进制搜索的大量工作.