我在cplusplus.com上阅读，通过传递迭代器作为参数来删除std::map中元素的操作是恒定时间。std :: map <t1, t2> ::擦除（迭代器位置）的工作？
如果我没有错（如果我是，请纠正我）迭代器基本上是指向映射中的元素++运算符只是返回当前元素的顺序后继我猜这就是排序结果通过遍历std::map实现。
现在如果地图是一棵红黑树，不应该删除一个元素（使用它的地址）是对数时间操作，我想知道它们是如何在恒定时间内完成的（除非存在高度浪费的内存要做到这一点）。
对于初学者，我会警惕任何来自cplusplus.com的信息;该网站已知有一些错误。
访问cppreference.com，我们得到复杂度为摊销恒定时间。这意味着即使单个擦除操作所花费的时间大于O（1），任何序列的操作都需要花费时间O（n）。
事实证明，从红/黑树插入或删除所需的时间最终计算如下：每次插入或删除花费时间O（log n）来找到节点的位置，但然后只有分期付款O（1）才能插入或删除元素。这意味着从红/黑树插入或删除节点所做的工作主要由确定该节点的位置所需的工作决定，而不是之后重新平衡树所需的工作。因此，如果您已经有了一个指向红/黑树的指针，并且想要删除该元素，那么只需执行分段O（1）工作即可删除该元素。每个单独的删除操作可能需要一些时间（最多O（log n）），但是在n个操作流中，完成的总工作数最多为O（n）。
请注意，该标准不要求std::map使用红色/黑色树。它可以使用另一种类型的数据结构（例如，splay tree，scapegoat tree或确定性的skiplist），这也保证了这种时间复杂性。有趣的是，并非所有的平衡二叉搜索树结构都可以支持平价的O（1）删除。例如，AVL tree没有这个保证。
希望这会有所帮助！
其实，cplusplus.com [也说]（http://www.cplusplus.com/reference/map/map/erase /）它是摊销常量。 – 2013-03-24 20:03:26
@ ArmenTsirunyan-啊，谢谢！这就是说，我仍然坚持我原来的主张。 :-) – templatetypedef 2013-03-24 20:03:53
不要误解我的意思。我不是卫冕cplusplus.com :) – 2013-03-24 20:05:18
如果您传递迭代器来映射以删除元素，则根据http://www.cplusplus.com/reference/map/map/erase/将其分摊到不变的时间。
摊销时间意味着“如果进行多项操作，每次操作所需的平均时间”。因此，可能会有一些操作需要比常量时间更长的时间，但如果您多次执行相同的操作，则会将其摊销不变。
相关http://stackoverflow.com/questions/12078795/stdmaperase-which-overload-is-faster – 2013-03-24 20:02:45