std::lower_bound 和 std::set::lower_bound 之间的 C++ 区别？

Question

最近，在处理C++ 编程问题时，我遇到了一些有趣的事情。我的算法使用了一个非常大的集合，并且会在其上使用 std::lower_bound 很多次。然而，在提交我的解决方案之后，与我在纸上所做的数学运算相反，以证明我的代码足够快，它最终变得太慢了。代码看起来像这样：

using namespace std;

set<int> s;
int x;

//code code code

set<int>::iterator it = lower_bound(s.begin(),s.end(),x);

然而，在从朋友那里得到使用 set::lower_bound 的提示后，该算法的运行速度比以前快得多，而且它符合我的计算。改变后的二分查找：

set<int>::iterator it = s.lower_bound(x);

我的问题是这两者有什么区别？为什么一个比另一个工作得快得多？ lower_bound 不应该是复杂度为 O(log2(n)) 的二分查找函数吗？在我的代码中，它最终比那慢得多。

Answer 1

std::lower_bound 是一种通用二进制搜索算法，适用于大多数 STL 容器。 set::lower_bound 旨在与 std::set 一起使用，因此它利用了 std::set.

的独特属性

由于std::set通常被实现为一棵红黑树，可以想象std::lower_bound遍历所有节点，而set::lower_bound只是遍历树。

Answer 2

std::lower_bound 始终保证 O(log n) 比较，只保证 O(log n) 次如果通过 RandomAccessIterator，而不仅仅是ForwardIterator 不提供恒定时间 std::advance.

相同算法的 std::set::lower_bound 实现能够使用结构的内部细节来避免这个问题。

Answer 3

std::set 通常被实现为一个自平衡树，其中包含一些类似列表的结构。知道了这个结构，std::set::lower_bound就会遍历树知道树结构的属性。这其中的每一步都意味着跟随左或右子分支。

std::lower_bound 需要运行类似于对数据进行二进制搜索的东西。然而，由于 std::set::iterator 是双向的，这要慢得多，需要在检查的元素之间完成很多增量。因此，元素之间所做的工作更加激烈。在这种情况下，算法将检查 A 和 B 中间的元素，然后调整 A 或 B 之一，找到它们中间的元素，然后重复。

Answer 4

看完std::lower_bound的API

On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

而且我认为 STL 集使用的是非随机访问迭代器，因此如果在 STL 集上使用它不会进行 O(log N) 二进制搜索

std::lower_bound 和 std::set::lower_bound 之间的 C++ 区别？

C++ Difference between std::lower_bound and std::set::lower_bound?

c++

algorithm

std

binary-search

c++11