std::map<t1, t2>::erase(iterator position) 的工作原理是什么？

Question

std::map<t1, t2>::erase(iterator position) 的工作原理是什么？

c++algorithmdata-structuresstlred-black-tree

9

我在 cplusplus.com 上读到，通过传递迭代器作为参数来删除 std::map 中的元素的操作是常数时间。如果我没错（请纠正我），迭代器基本上是指向映射中元素的指针，并且 ++ 运算符只返回当前元素的顺序继承者，我想这就是在遍历 std::map 时实现排序结果的方式。现在，如果 map 是一个红黑树，那么使用其地址删除一个元素应该是对数时间操作，我不知道他们如何以常数时间完成（除非有一种高度浪费内存的替代方法）。

- Rampal Chaudhary

与https://dev59.com/V2fWa4cB1Zd3GeqPiZMx相关 - Shafik Yaghmour

2个回答

2

如果您将一个迭代器传递给map的erase函数来删除元素，则根据http://www.cplusplus.com/reference/map/map/erase/，它是摊销常数时间。

摊销常数时间意味着“每个操作所花费的平均时间，如果您执行许多操作”。因此，可能会有一些操作比常数时间更长，但如果您重复执行相同的操作许多次，则其时间是摊销常数。

- taocp

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

作为开头，我会对从cplusplus.com获取的信息持谨慎态度；这个网站已知存在一些错误。

访问cppreference.com，我们得知复杂度是摊销常数时间。这意味着任何n个erase操作序列应该花费O(n)的时间，即使单个erase操作花费的时间大于O(1)。

插入或删除红黑树所需的时间实际上是按照以下方式计算的：每次插入或删除需要O(log n)的时间来找到节点的位置，但是只需要摊销O(1)的工作量来插入或删除元素。这意味着在红黑树中插入或删除节点所做的工作由查找节点位置所需的工作主导，而不是之后重新平衡树所需的工作。因此，如果您已经有指向红黑树的指针并想要删除该元素，则仅需进行摊销O(1)的工作即可删除该元素。每个单独的删除可能需要一些时间（最多为O(log n)），但在n个操作流中完成的总工作量最多为O(n)。

请注意，标准并不要求std::map使用红黑树。它可以使用另一种数据结构（比如splay tree、scapegoat tree或确定性skiplist），也能保证这种时间复杂度。有趣的是，并非所有平衡二叉搜索树都支持分摊O(1)删除。例如，AVL tree就没有这个保证。

希望这能帮到你！