logo标签列表

C++中的begin/end/rbegin/rend函数在std::set、std::map等容器中执行时是否以常数时间复杂度运行？

c++stl
9

对于像std::set和std::map这样的数据类型，查找时间为对数时间，实现是否需要维护begin和end迭代器？访问begin和end是否意味着可能会发生对数时间的查找？

我一直认为begin和end始终在常数时间内发生，但是我在Josuttis中找不到任何证实。现在我正在处理需要非常关注性能的工作，我想确保涵盖我的所有基础知识。

谢谢

6个回答
10
它们在恒定时间内发生。我正在查看ISO/IEC 14882:2003标准的第466页：
表65-容器要求
a.begin();（常数复杂度）
a.end();（常数复杂度）
表66-可逆容器要求
a.rbegin();（常数复杂度）
a.rend();（常数复杂度）
6
5
在C++标准中，23.1（容器要求）的表格65将begin()和end()列为需要恒定时间。如果您的实现违反了这一点，则不符合规范。
3

看一下代码，你可以在GNU libstdc++中看到std::map中的迭代器。

std::map

你会发现所有的end、rend、cend等都是在常数时间内实现的。

1

但要小心hash_map。begin（）不是常量。

0

对于std::set

begin: 常量, end: 常量, rbegin: 常量, rend: 常量,

对于std::map

它们也都是常量。

如果您有任何疑问，请查看www.cplusplus.com。

1
不要过分依赖cplusplus.com。 - Jagannath
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接