c++ - std::lower_bound 与 std::set 的时间复杂度是多少？

Question

我知道有 std::set::lower_bound 并且时间复杂度是 O(log)，我看到 std::lower_bound 在 std::set 上运行时比 std::set::lower_bound 慢得多。

我用谷歌搜索并找到了这个:

http://en.cppreference.com/w/cpp/algorithm/lower_bound http://en.cppreference.com/w/cpp/iterator/advance

所以很明显，因为 std::advance 对于 set::iterator 是线性的，所以整个 std::lower_bound 需要直到 O(n)。

但是，当我使用它时，它的运行速度比 O(n) 快得多(一些 friend 也这么说)，谁能解释为什么或告诉我它不是那样的。

Answer 1

std::lower_bound() 的保证复杂度在非随机访问迭代器上为 O(n)。如果该算法检测到搜索是在一个有序的关联容器上进行的，它可能会利用树结构可能实现更好的复杂性。我不知道是否有任何实现这样做。