对于像 std::set 和 std::map 这样的数据类型，在对数时间内进行查找，是否需要实现来维护开始和结束迭代器？访问开始和结束是否意味着可能在对数时间内发生的查找？
我一直认为开始和结束总是在恒定的时间内发生，但是我在 Josuttis 中找不到任何证实。现在我正在做一些我需要对性能保持冷静的事情，我想确保覆盖我的基础。
谢谢
Doug T.
问问题
2888 次
6 回答
9
它们发生在恒定的时间。我正在查看 ISO/IEC 14882:2003 标准的第 466 页：
表 65 - 容器要求
a.开始（）； （恒定的复杂性）
a.end(); （恒定的复杂性）
表 66 - 可逆容器要求
a.rbegin(); （恒定的复杂性）
a.rend(); （恒定的复杂性）
于 2008-09-17T14:16:45.430 回答
5
是的，根据http://www.cplusplus.com/reference/stl/，begin ()、end() 等都是 O(1)。
于 2008-09-17T14:12:05.347 回答
4
在 C++ 标准中，23.1（容器要求）中的表 65 将 begin() 和 end() 列为需要恒定时间。如果您的实现违反了这一点，则它不符合要求。
于 2008-09-17T14:13:37.730 回答
2
于 2008-09-17T14:14:45.590 回答
1
不过要小心 hash_map 。begin() 不是恒定的。
于 2008-09-17T14:58:55.530 回答
0
于 2008-09-17T14:14:55.230 回答