Why is std::unordered_set rehashed even if the load factor limit is not broken?

Question

According to cppreference,

Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count().

In addition, [unord.req]/15 has similar rules:

The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container's bucket count, and z is the container's maximum load factor.

However, consider the following example:

#include <unordered_set>
#include <iostream>

int main()
{
    std::unordered_set<int> s;
    s.emplace(1);
    s.emplace(42);
    std::cout << s.bucket_count() << ' ';
    std::cout << (3 > s.max_load_factor() * s.bucket_count()) << ' ';
    s.emplace(2);
    std::cout << s.bucket_count() << ' ';
}

With GCC 8.0.1, it outputs

3 0 7

This means after emplacing 2, a rehashing occurs though the new number of elements (3) is not greater than max_load_factor()*bucket_count() (note the second output is 0). Why does this happen?

Answer 1

You're confusing the fact that the bucket_count() has changed with the invalidation of iterators. Iterators are only invalidated in case of rehash, which will not be one if new number of elements is less than or equal to max_load_factor()*bucket_count() (btw if size()>max_load_factor()*bucket_count() rehashing can occur, but doesn't have to).

As this was not the case in your example, no rehashing occurred and iterators remain valid. However, the bucket count had to be increased to accommodate the new element.

I experimented a bit (expanding on your code) with Mac OSX's clang, which kept the iterators valid even after rehash(size()) (which did change the element's bucket association, tested directly by iterating over the buckets and printing their contents).