c++ - 迭代 std::set/std::map 的时间复杂度是多少？

Question

遍历 std::set/std::multiset/std::map/ 的时间复杂度是多少std::multimap?我相信它在集合/ map 的大小上是线性的，但不太确定。语言标准中有规定吗？

Answer 1

在 draft C++11 standard N3337答案可以在 § 24.2.1 第 8 段中找到:

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).

由于对迭代器的每个操作都必须是常数时间，因此遍历 n 元素必须是 O(n)。