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

Question

迭代

std::set

/

std::multiset

/

std::map

/

std::multimap

的时间复杂度是多少？我相信它与集合/地图的大小是线性的，但不太确定。语言标准中有规定吗？

Answer 1

在C++11工作草案中，可以在[iterator.requirements.general] p8:

中找到答案

所有类别的迭代器只需要那些函数 对于给定类别可以在恒定时间内实现（摊销）。

由于迭代器上的每个操作都必须是恒定时间，因此迭代

n

元素必须是

O(n)

。

Answer 2

我相信它与集合/地图的大小是线性的，但事实并非如此 当然。

这是正确的。迭代整个集合或映射是

O(N)