为什么std::map单迭代器erase是均摊常数，范围版本复杂度含log项？

std::map的主流实现都基于红黑树（自平衡二叉搜索树），标准给出的复杂度约定也是基于这一实现模型：

• 你已经理解的单迭代器重载erase(iterator pos)，均摊常数复杂度的核心原因是：迭代器直接指向待删除的红黑树节点，不需要额外查找定位，删除节点后的树重平衡开销为均摊常数，所以整体是均摊O(1)。
• 范围重载erase(iterator first, iterator last)多出来的log(c.size())开销，来源于底层红黑树的结构操作：
  • [first, last)对应红黑树中序遍历的一段连续节点，在批量删除前，实现需要先定位到包含所有待删除节点的最小子树边界，同时找到待删除区间的前驱、后继节点，用于后续拼接删除后剩下的树结构，这个定位和预处理操作的复杂度和整棵树的大小相关，为固定的O(log c.size())，和待删除元素的数量无关。
  • 预处理完成后，批量遍历删除区间内所有节点的开销为O(std::distance(first, last))，这个过程不需要逐次执行单节点删除后的重平衡操作，实际常数开销比循环调用单迭代器erase更低。

内容的提问来源于stack exchange，提问作者Facundo Astiz