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