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

Question

我知道存在std::set::lower_bound并且时间复杂度为O(log)，并且我发现这比在 上运行时std::lower_bound慢得多。std::set::lower_boundstd::set

我用谷歌搜索并发现了这个：

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)（一些朋友也是这么说的），任何人都可以解释为什么或告诉我它不是那样的。

Answer 1

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