c++ - std::map::erase(iterator position) 的工作？

Question

我阅读了cplusplus.com通过将迭代器作为参数传递来删除 std::map 中元素的操作是常量时间。

如果我没记错(请纠正我)，迭代器基本上是指向 map 中元素的指针，带有 ++ 运算符，只返回当前元素的有序后继我想这就是遍历 std::map 时排序结果的实现方式。

现在如果 map 是一棵红黑树，删除一个元素(使用它的地址)不应该是对数时间操作，我想知道他们是如何在恒定时间内完成的(除非有一个高度内存浪费的替代方案这样做)。

Answer 1

首先，我会对您从 cplusplus.com 获得的任何信息保持警惕；该网站已知有一些错误。

来访cppreference.com ，我们得到复杂度是 摊销 常数时间。这意味着任何 n 个erase 操作序列都应该花费 O(n) 的时间，即使单个删除操作花费的时间大于 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 ，例如，没有此保证。

希望这对您有所帮助!