C++对std :: set,std :: map等的常量时间开始/结束/ rbegin/rend执行吗？

Question

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

我一直认为开始和结束总是在恒定的时间内发生,但我在Josuttis找不到任何确认.现在我正在做一些我需要对表演进行肛门的事情,我想确保覆盖我的基础.

谢谢

Answer 1

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

表65 - 集装箱需求

a.begin(); (不断复杂)

a.end(); (不断复杂)

表66 - 可逆容器要求

a.rbegin(); (不断复杂)

a.rend(); (不断复杂)

Answer 2

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

Answer 3

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