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