对于std :: set和std :: map这样的数据类型，其中以对数时间进行查找，是否需要实现来维护begin和end迭代器？访问开始和结束是否意味着可能会在对数时间内进行查找？

我一直以为开始和结束总是在恒定的时间发生，但是在Josuttis中找不到对此的任何确认。既然我正在做一些需要对性能进行分析的工作，那么我想确保掩盖了自己的基础。

谢谢

解决方案

回答

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

回答

在C ++标准中，表23.1(容器要求)中的表65列出了begin()和end()需要恒定的时间。如果实现违反了此要求，则说明不符合要求。

回答

只需查看代码，即可在GNU libstdc ++的std :: map中看到迭代器

std :: map

我们会看到所有end rend cend ...都是在恒定时间内实现的。

回答

对于std :: set

开始：常数，结束：常数，
rbegin：常量，
撕裂：恒定，

对于std :: map

他们也是不变的(所有人)

如有任何疑问，请访问www.cplusplus.com

回答

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

表65容器要求

a.begin(); (不变的复杂性)

a.end(); (不变的复杂性)

表66可逆容器要求

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

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

回答

但是请谨慎使用hash_map。 begin()不是常数。