Working of std::map<t1, t2>::erase(iterator position)?

Question

I read on cplusplus.com that the operation to delete an element in a std::map by passing the iterator as argument is constant time.

If I am not wrong(and please correct me if I am) the iterators basically are pointers to the elements in the map with ++ operator just returning the in-order successor of the current element I guess that's how a sorted result is achieved on traversal of std::map.

Now if the map is a red black tree, shouldn't the deletion of an element(using its address) be logarithmic time operation, I wonder how they do it in constant time (unless there is a highly memory wasteful alternative to do that).

Answer 1

If you pass an iterator to map to remove the element, it is amortized constant time according to http://www.cplusplus.com/reference/map/map/erase/.

Amortized constant time means that "average time taken per operation, if you do many operations". Therefore, there may be some operation that takes longer than constant time, but if you do the same operation many many times, it is amortized constant.

Answer 2

For starters, I'd be wary of any information you get from cplusplus.com; the site is known to have some errors on it.

Visiting cppreference.com, we get that the complexity is amortized constant time. This means that any sequence of n erase operations should take time O(n), even if an individual erase operation takes time that is greater than O(1).

It turns out that the time required to insert or delete from a red/black tree ends up being computed as follows: each insertion or deletion takes time O(log n) to find the position for the node, but then does only amortized O(1) work to insert or remove the element. This means that the work done inserting or deleting a node from a red/black tree is dominated by the work required to figure out where that node goes, rather than the work required to rebalance the tree afterwards. As a result, if you already have a pointer into a red/black tree and want to delete that element, you only have to do amortized O(1) work to delete the element. Each individual delete might take a bit of time (at most O(log n)), but over a stream of n operations the total work done is at most O(n).

Note that the standard doesn't require that std::map use a red/black tree. It could use another type of data structure (say, a splay tree, scapegoat tree, or deterministic skiplist) that also guarantees this time complexity. Interestingly, though, not all balanced binary search tree structures can support amortized O(1) deletion. The AVL tree, for example, does not have this guarantee.

Hope this helps!