C++ does begin/end/rbegin/rend execute in constant time for std::set, std::map, etc?对于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中看到迭代器
您会看到所有end rend cend ...都是在恒定时间内实现的。 但是请谨慎使用hash_map。 begin()不是常数。 对于std :: set
开始：常数，结束：常数， 对于std :: map 他们也是不变的(所有人) 如有任何疑问，请访问www.cplusplus.com |
