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

Question

什么是迭代std::set/ std::multiset/ std::map/ 的时间复杂度std::multimap？我相信它在集合/地图的大小上是线性的,但不是那么肯定.是否在语言标准中指定？

Answer 1

在C++ 11标准N3337草案中,答案可以在第24.2.1段第8段中找到:

所有迭代器类别仅需要在恒定时间内(摊销)可以为给定类别实现的那些函数.

由于迭代器上的每个操作必须是恒定时间,因此迭代n元素必须是O(n).

如果map/set被实现为具有父指针的二叉树,则遍历所有元素的迭代将最多访问每个树节点3次.如果实现是带有父指针的b树,则每个节点最多访问2*n + 1次,n是节点中元素的数量.在这两种情况下,这意味着每个迭代步骤的平均时间复杂度恒定.我不知道有任何其他合规的方法来实现map/set. (2认同)
实际上，对于“ std :: set”，“ std :: multiset”，“ std :: map`，`std :: multimap`（如果它们被实现为红黑树（这是最常见的情况）），查找下一个/上一个有序元素的最坏情况的复杂度是O（log N）。当然，实际上，平均情况是摊销常数。 (2认同)

Answer 2

我相信它在集合/地图的大小上是线性的,但不是那么肯定.

那是正确的.迭代整个集合或地图是摊销的 O(N)

你为什么强调*摊销*？对于所有已知的实现，它都是“O(N)”。证明很简单。容器`set` 和`map` 是使用红黑树实现的。每次从一个节点移动到另一个节点时，只需在两个节点之间画一条线。完成迭代后，您将看到所有行都加倍，并且您访问了每个节点两次。 (5认同)
@Elliott 这是正确的。查找二叉树中的下一个最高元素需要 O(log N) 时间。 (2认同)