代码之家 › 专栏 › 技术社区 › Abdullah Kassar

std::upper_bound()是线性的吗?c++

upperbound binary-search time-complexity performance c++

2

Abdullah Kassar · 技术社区 · 2 年前

我正在阅读USACO Silver上的指南,谈论分类套装,我偶然发现 this warning ( 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) ?

2 回复 | 直到 2 年前

1

7

Ted Lyngmo 2 年前

这是因为 std::set 不支持随机访问迭代器。为了从 a 到 a + 200 算法必须增加 一 200次。

因此 std::设置 具有用于查找的成员函数 upper_bound 和 lower_bound 高效。

2

1

Kelly Bundy 2 年前

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