Why std::unordered_map::rehash() is allowed to invalidate iterators?

Question

Visual Studio (2015) implementation does not invalidate any iterators (rehash() reorders internal std::list, keeping all iterators valid).

Are there other implementations, which invalidate iterators (and achieve better performance, even with the same complexity)?

Invalidating iterators on std::unordered_map::rehash() sometimes can limit developers (e.g. I'm trying to implement LRU cache with std::unordered_map only: with node's value having iterators to the container). But does the possibility to invalidate iterators allow to implement std::unordered_map::rehash() better?

Answer 1

Thanks to @DanielLangr for the discussion above,

I think, this requirement comes with std::unordered_map::[const_]iterator definition as LegacyForwardIterator (and not LegacyBidirectionalIterator). And an implementation with better memory footprint using internal std::forward_list or similar (instead of VS' std::list) is impossible without invalidating iterators in rehash() (probably, except end()).

• This better memory footprint implementations may add some [simple] assembly instructions here and there (also may save some in other places), or may have larger sizeof(std::unordered_map::[const_]iterator), but it is definitely the right thing to define std::unordered_map requirements as they are, and leave all those considerations to implementers.