c++ - std::map 的工作::erase（迭代器位置）？

Question

我在cplusplus.comstd::map上读到，通过将迭代器作为参数传递来删除 a 中的元素的操作是常数时间。

如果我没有错（如果我错了，请纠正我）迭代器基本上是指向地图中元素的指针，++运算符只返回当前元素的有序后继我猜这就是在遍历时实现排序结果的方式std::map.

现在，如果地图是一棵红黑树，那么删除元素（使用其地址）不应该是对数时间操作，我想知道他们如何在恒定时间内做到这一点（除非有一个非常浪费内存的替代方案） .

Answer 1

对于初学者，我会警惕您从 cplusplus.com 获得的任何信息；该网站已知有一些错误。

访问cppreference.com，我们了解到复杂性是摊销的常数时间。这意味着任何 nerase次操作的序列都应该花费时间 O(n)，即使单个擦除操作花费的时间大于 O(1)。

事实证明，从红/黑树中插入或删除所需的时间最终计算如下：每次插入或删除需要时间 O(log n) 才能找到节点的位置，但随后只摊销 O( 1) 努力插入或移除元素。这意味着从红/黑树中插入或删除节点所完成的工作主要是确定该节点去哪里所需的工作，而不是事后重新平衡树所需的工作。结果，如果您已经有一个指向红/黑树的指针并想要删除该元素，则只需执行摊销 O(1) 工作即可删除该元素。每个单独的删除可能需要一些时间（最多 O(log n)），但在 n 个操作的流中，完成的总工作最多为 O(n)。

请注意，该标准不要求std::map使用红/黑树。它可以使用另一种类型的数据结构（例如，展开树、替罪羊树或确定性跳过列表），也可以保证这种时间复杂度。然而，有趣的是，并非所有平衡二叉搜索树结构都支持分期 O(1) 删除。例如，AVL 树没有这种保证。

希望这可以帮助！

Answer 2

如果您将迭代器传递给 map 以删除元素，则根据http://www.cplusplus.com/reference/map/map/erase/将其摊销为常数时间。

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