C++ 是否在 std::set、std::map 等的恒定时间内执行 begin/end/rbegin/rend ？

Question

对于诸如 std::set 和 std::map 之类的数据类型，其中查找发生在对数时间内，是否需要实现来维护开始和结束迭代器？访问开始和结束是否意味着可能在对数时间内发生查找？

我一直假设开始和结束总是在恒定时间内发生，但是我在 Josuttis 中找不到任何对此的确认。现在我正在做一些需要对性能进行严格控制的事情，我想确保覆盖我的基础。

谢谢

Answer 1

它们以恒定的时间发生。我正在查看 ISO/IEC 14882:2003 标准的第 466 页：

表 65 - 容器要求

a. 开始(); （复杂性恒定）

a.end(); （复杂性恒定）

表 66 - 可逆容器要求

a.rbegin(); （复杂性恒定）

a. 撕裂(); （复杂性恒定）

Answer 2

是的，根据 http://www.cplusplus.com/reference/stl/, 、begin()、end() 等都是 O(1)。

Answer 3

在 C++ 标准中，23.1（容器要求）中的表 65 列出了要求恒定时间的 begin() 和 end()。如果您的实现违反了这一点，则它不符合要求。

Answer 4

看看代码就可以了，在这里你可以看到GNU libstdc++中std::map中的迭代器

std::map

你会看到一切都结束了……都是在恒定时间内执行的。

Answer 5

不过要小心 hash_map 。begin() 不是常量。

Answer 6

对于 std::set

开始：常数，结束：常数，rbegin：恒定，渲染：持续的，

对于 std::map

它们也是恒定的（全部）

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