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

[Harrison56]

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).

[JLBorges]

> If I am not wrong(and please correct me if I am) the iterators basically are pointers

Iterators are pointer-like: from an iterator we can get to the element 'pointed to' in constant time. When deleting an element given the iterator, the map can get to the node containing the element in constant time; the actual deletion of the node would take amortised constant time.

Deleting an element given the key takes logarithmic time; getting to the node containing the key is what takes logarithmic time.

https://en.cppreference.com/w/cpp/container/map/erase#Complexity

[jonnin]

if it helps, unordered map has constant erase time if you do it by key.

[lastchance]

If the tree is to be re-balanced is that really constant time?

[JLBorges]

Average O(1), worst case O(N).

Worst case is the extreme situation when we have a really bad hash, with all N elements ending up in the same bucket. There is no rehashing on erase.

[lastchance]

But if a red-black tree was balanced before erase, then surely the worst case to rebalance after erase is O(log N)? (Proportional to the depth of the tree.)

[JLBorges]

std::unordered_map<> is not a red-black tree; it is a bucket-based hash table.

It may require rehashing on insert (when maximum load factor is exceeded).

[lastchance]

Never mind; I thought the original post was about std::map, not std::unordered_map.

[JLBorges]

Re std::map - "the actual deletion of the node would take amortised constant time."
http://www.cplusplus.com/forum/general/280722/#msg1213812

[jonnin]

Never mind; I thought the original post was about std::map, not std::unordered_map.
it was! I dragged UM into it, in case it was useful to the OP.

[lastchance]

Yeah, and I wasn't thinking about deleting a node - that's clearly O(1) if you know its memory address - I was interested in the re-balance time afterward, to keep it a red-black tree.

[jonnin]

I don't know how c++ does it. normally you just leave trees alone, if you delete you just mark it as such, and rebuild it / rebalance it once in a rare while. its still red/black that way, counting the 'deleted' nodes.

[JLBorges]

For the erase accepting a single iterator, the standard specifies amortised constant time;
while the look up for a key is (always) in logarithmic time.

The tree is rebalanced (if required) after the erasure; otherwise, the complexity guarantees for iterator traversal could be violated.

[lastchance]

@Harrison56,
I think the straight answer to your question is that the complete operation, including rebalancing, is O(1) on average ("amortised"), but has a worst case of O(log N) (proportional to depth of tree).

Somehow, the thread seems to have got diverted to look-up and unordered maps, neither of which was asked.