CODEWITHSUNDEEP
c++c++11unordered-maperase-remove-idiom
imreal
imreal

Reputation: 10358

unordered_map rehasing on erase()

I am not entirely clear on whether unordered_map is allowed to perform a rehash when doing an erase()

It is pretty clear that rehashing can happen during insert() thus invalidating all iterators and references:

http://en.cppreference.com/w/cpp/container/unordered_map/insert

But erase() seems to preserve all iterators and references except for the ones erased:

http://en.cppreference.com/w/cpp/container/unordered_map/erase

However, that last page and the Standard, indicate that erase() worst execution time is O(size). What operation can take linear time to complete and not modify the container in a way it invalidates iterators?

This post suggests that iterators are invalidated during erasure: http://kera.name/articles/2011/06/iterator-invalidation-rules-c0x/

I also read somewhere that a future proposal will allow rehashing on erase(). Is that true?

If indeed rehashing occurs, the old iterate and erase algorithm is wrong right?

Upvotes: 2

Views: 901

Answers (1)

BoBTFish
BoBTFish

Reputation: 19767

If you have a very bad hash, or pathological data, all of the elements can end up in one bucket, making it an O(n) traversal to locate/remove the element.

It is perfectly legal to implement a std::unordered_map using a (singly-)linked-list for the elements: we can see that its iterator type is only required to fulfil the ForwardIterator concept. This makes a linear traversal necessary to remove an element within a bucket, even when passing the iterator.

This is the operation that may take O(n) time, not rehashing.

Upvotes: 7

Related Questions