为什么 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

这是因为

std::set

不支持随机访问迭代器。为了从

a

到

a + 200

，算法必须将

a

增加 200 倍。

因此，

std::set

具有有效查找

upper_bound

和

lower_bound

的成员函数。

Answer 2

来自cppreference：

对于非 LegacyRandomAccessIterators，迭代器增量的数量是线性的。值得注意的是，std::map、std::multimap、std::set 和 std::multiset 迭代器不是随机访问