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

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

upperbound binary-search time-complexity performance c++

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 年前

Ted Lyngmo 2 年前

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

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

Kelly Bundy 2 年前

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

推荐文章

AstralHex · 矩阵乘法代码工作不正常

9 月前

Baba Dan Constantin · SSE4.1在矩阵4x4乘法上比SSE3慢?

9 月前

Giogre · 为包含许多数值字段的简单“struct”重载比较运算符

9 月前

einpoklum · 定义一个并不真正提供now()函数的std::chrono Clock是“合法的”吗?

9 月前

Fishie · 作为类成员的智能指针是否仍然自动释放?[关闭]

9 月前

Die4Toast · 递归调用成员箭头运算符->

9 月前

Angle.Bracket · 如何用C++将UTF-8文件名写入MS Windows控制台?

9 月前

Anka HanÄ±m · 关于结构和动态数组地址的问题

10 月前

Adam Barnes · 我如何定义一个基于constexpr函数返回值进行限制的概念?

10 月前

user2138149 · 为什么我不能获取包含多个元素的结构体中某些元素的地址?[副本]

10 月前