Iterator invalidation with unordered_set/unordered_multiset

Question

I know that unordered_set might invalidate iterators when elements are inserted:

"If rehashing occurs (due to the insertion), all iterators are invalidated."

It is clear, because we have hash table with buckets, but why does unordered_multiset not invalidate iterators?
I think the implementation of unordered_set is almost identical with the implementation of unordered_multiset (hash table with buckets).

Answer 1

There is actually no difference in this respect between std::unordered_set and std::unordered_multiset.

As you can see in the unordered_multiset::insert documentation, it contains the exact same note as unordered_set::insert:

If rehashing occurs (due to the insertion), all iterators are invalidated.

BTW - they are also identical in the case where there is no rehashing:

Otherwise (no rehashing), iterators are not invalidated.

Note that it doesn't mean the two containers will always behave the same when it comes to invalidating iterators - because the implementation has some freedom (tweaking buckets count etc. which can affect rehashing - see @TonyDelroy's comment below).

Answer 2

In the C++ Standard Library, the behavior of unordered_set and unordered_multiset regarding iterator invalidation during insertions might seem similar, but there are key differences in how duplicates are handled.

unordered_set:

In an unordered_set, each element is unique, and the insert operation might cause rehashing to occur if the load factor threshold is exceeded. Rehashing involves changing the number of buckets in the hash table, which can invalidate iterators because the elements might be moved to new locations. unordered_multiset:

In an unordered_multiset, duplicate elements are allowed. When you insert an element, the insert operation adds it to the appropriate bucket without considering rehashing due to load factors. Since the number of buckets doesn't change during regular insertions (only when the container is resized), iterators are generally not invalidated during insertions. The existing elements in a bucket are not affected by the insertion of a new element, and the iterator can still point to the correct bucket. In summary, the key difference lies in the handling of duplicates. In an unordered_multiset, insertions of new elements don't trigger rehashing like in unordered_set, and therefore, iterators are less likely to be invalidated during regular insertions. It's always important to check the specific documentation or standard for the C++ implementation you are using, as details can vary between different standard library implementations.

and yes there is a difference, it might not be that much but its still a pretty valid one @wohlstad