我在cplusplus.com上看到，通过传递迭代器作为参数来删除std::map中的元素的操作是常数时间。
如果我没有错(请纠正我，如果我是)，迭代器基本上是指向映射中元素的指针，++操作符只是返回当前元素的顺序后继，我想这就是如何在std::map的遍历上实现排序结果。
现在，如果映射是一个红黑树，不应该删除一个元素(使用它的地址)是对数时间操作，我想知道他们是如何在常数时间内完成的(除非有一个高度内存浪费的替代方法)
对于初学者，我会警惕你从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使用红/黑树。它可以使用另一种类型的数据结构(例如，张开树、替罪羊树或确定性跳过列表)，这些数据结构也保证了这种时间复杂度。有趣的是，并非所有平衡二叉搜索树结构都支持平摊O(1)删除。例如，AVL树就没有这种保证。
希望这对你有帮助!
如果向map传递迭代器以删除元素，则根据http://www.cplusplus.com/reference/map/map/erase/平摊常数时间。
平摊常数时间意味着"如果你做很多操作，每次操作所花费的平均时间"。因此，可能会有一些操作花费的时间比常量时间长，但如果你多次执行相同的操作，它就会平摊为常量。