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

Question

对于 std::set 和 std::map 等以对数时间查找的数据类型，实现是否需要维护开始和结束迭代器？访问 begin 和 end 是否意味着查找可能以对数时间发生？

我一直假设开始和结束总是在常数时间内发生，但是我在 Josuttis 中找不到任何对此的证实。既然我正在做一些我需要对性能有所了解的事情，我想确保涵盖我的基础。

谢谢

Answer 1

它们发生在常数时间内。我正在查看 ISO/IEC 14882:2003 标准的第 466 页:

表 65 - 容器要求

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

a.end(); (恒定的复杂性)

表 66 - 可逆容器要求

a.rbegin(); (恒定的复杂性)

a.rend(); (恒定的复杂性)