遍历 std::set/std::map 的时间复杂度是多少？

Question

遍历 std::set/std::multiset/std::map/std::multimap 的时间复杂度是多少？我认为它是与 set/map 的大小成线性关系，但不太确定。它是否在语言标准中有明确规定？

- updogliu

---

整个容器的迭代至少是O(n)（我想真的很愚蠢的实现可能会使它变得更糟）。 - Chad

Answer 1

在C++11工作草案中，答案可以在[iterator.requirements.general] p8中找到：

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

由于迭代器上的每个操作都必须是常数时间，所以遍历n个元素的时间复杂度必须是O(n)。

- Mark Ransom

---

如果将map/set实现为带有父指针的二叉树，则遍历所有元素的迭代最多会访问每个树节点3次。如果实现为带有父指针的B-树，则每个节点最多会被访问2*n + 1次，其中n是节点中元素的数量。在这两种情况下，这意味着每个迭代步骤的平均时间复杂度都是常数级别的。我不知道其他符合要求的map/set实现方式。 - WaltK

实际上，对于 std::set、std::multiset、std::map 和 std::multimap，如果它们被实现为红黑树（这是最常见的情况），则查找下一个/前一个按顺序的元素的最坏复杂度为O(log N)。当然，在实践中，平均情况是摊销常数。 - plasmacel

Answer 2

我认为它是基于集合/映射的大小呈线性增长的，但并不确定。

那是正确的。遍历整个集合或映射的时间复杂度是O(N)

- Chris Dargis

---

为什么你强调摊销？对于所有已知的实现，它都是精确的O(N)。证明非常简单。容器set和map是使用红黑树实现的。每次从一个节点移动到另一个节点时，只需在它们之间画一条线。迭代完成后，您将看到所有的线都成双出现，每个节点都被访问了两次。 - Igor Mikushkin

@Elliott 这是正确的。在二叉树中查找下一个最高元素需要 O(log N) 的时间。 - Igor Mikushkin

@IgorMikushkin。因为您的两条评论，以及进一步思考，我可以看出它大致是2n的时间，因此是O(n)。我也意识到我关于如何找到元素的描述是错误的。感谢您的帮助-我总是假设它是O(n*log(n))。谢谢！ - Elliott