关于stl：C ++，std :: set，std :: map等的开始/结束/ rbegin / rend是否在恒定时间内执行？

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

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

谢谢

---

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

表65-容器要求

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

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

表66-可逆容器要求

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

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

---

是的，根据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 ...都是在恒定时间内实现的。

---

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

---

对于std :: set

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

对于std :: map

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

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

---