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的提示之后，所讨论的算法比以前更快地工作了waaaaaaaay，它遵循了我的数学思想。更改后的二进制搜索：

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

我的问题是两者之间有什么区别？为什么一个工作比另一个工作快得多？Lower_bound是否应该是具有复杂度O（log2（n））的二进制搜索函数？在我的代码中，它最终比这要慢。

Answer 1

std::set通常将其实现为自平衡树，并在其中绑定一些类似列表的结构。知道此结构，std::set::lower_bound将遍历树，知道树结构的属性。每个步骤仅意味着遵循左或右子分支。

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