C++中std::lower_bound和std::set::lower_bound有什么区别？

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))的复杂度的二分查找函数吗？但在我的代码中，它的速度比这慢得多。

- Leonard Inkret

---

如果这是某种竞赛问题，请注意，您始终会想要利用集合中找到的 lower_bound 而不是通用版本（通用版本几乎总是更慢）。 - ra1nmaster

可能是为什么两个看似相同的lower_bound()方法有不同的处理时间的重复问题。 - RiaD

Answer 1

std::set通常被实现为一种自平衡树，其中包含一些类似于列表的结构。了解这个结构后，std::set::lower_bound会遍历该树，并知道树结构的属性。在每一步中，只需要跟随左侧或右侧的子分支。

std::lower_bound需要在数据上运行类似于二分搜索的算法。然而，由于std::set::iterator是双向迭代器（而不是随机访问迭代器），因此这样做会慢得多，需要在检查元素之间执行大量的增量操作。因此，在元素之间执行的工作要更加强烈。在这种情况下，算法将检查介于A和B之间的元素的一半，然后调整A或B中的一个，找到它们之间的中间元素，并重复这个过程。

- Ryan Haining

---

哦，我明白了，谢谢大家给我解释。我现在会记住始终使用 set::lower_bound 和 sets 了。 - Leonard Inkret

Answer 2

阅读完std::lower_bound的API之后：

在非随机访问迭代器上，迭代器的前进平均会使N增加额外的线性复杂度。

我认为STL set使用非随机访问迭代器，因此如果在STL set上使用，它并不会进行O(log N)的二分查找。

- shole

---

你是正确的，std::set::iterator 是双向迭代器，而不是随机访问迭代器。 - Ryan Haining

Answer 3

std::lower_bound 是一个通用的二分查找算法，旨在与大多数STL容器一起使用。 set::lower_bound 旨在与 std::set 一起使用，因此它利用了 std::set 的独特属性。

由于 std::set 通常被实现为红黑树，因此可以想象 std::lower_bound 在所有节点上迭代，而 set::lower_bound 只是沿着树向下遍历。

- yizzlez

Answer 4

std::lower_bound总是保证O(log n)的比较次数，只有当传递一个RandomAccessIterator而不是只有一个ForwardIterator时才保证O(log n)时间复杂度，因为后者不提供常数时间的std::advance。

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

- o11c