为什么 std::upper_bound() 具有线性复杂度？

Question

我正在阅读 USACO Silver 上有关排序集的指南，我遇到了这个警告（s是std::set整数）：

警告！
假设我们替换s.upper_bound(7)为upper_bound(begin(s),end(s),7)，这是我们在先决条件模块中用于向量的语法。这仍然会输出预期的结果，但它的时间复杂度与集合的大小是线性的s，而不是对数的，所以一定要避免它！

他们的意思是什么 ？

   upper_bound(s.begin(), s.end(), 7 ); // O(n) ?
   s.upper_bound(7);                    // O(log N) ?

Answer 1

这是因为 astd::set不支持随机访问迭代器。为了得到 ，a算法a + 200就必须增加a200 倍。

因此，std::set具有查找upper_bound和lower_bound高效的成员函数。