C++ Logo

std-discussion

Advanced search

Unordered associative containers and infinity max load factor

From: Christian Mazakas <christian.mazakas_at_[hidden]>
Date: Tue, 13 Sep 2022 09:59:00 -0700
I'm beginning to think that there might be a potential ambiguity in the
requirements
of max_load_factor() and reserve() for the unordered associative containers.

See:
https://eel.is/c++draft/unord.req#lib:max_load_factor,unordered_associative_containers_

There's no mention of how to handle a value of infinity.

This can have somewhat surprising effects in implementations.

For example, an implementation of reserve() might be as is literally
specified in the standard:
    a.rehash(ceil(n / a.max_­load_­factor()))

This has the unfortunate caveat that for all positive values of n, we're
invoking `a.rehash(0)`.

This means that if `a.bucket_count() == 0`, `a.reserve(1000)` can legally
be a no-op and
`a.bucket_count() == 0` continues to hold. This can be observed in libc++:
https://godbolt.org/z/EdY9d5r6G

This seems to be a defect in wording as I assume the intention was that
`reserve(n)` for some
positive n would allocate at least 1 bucket.

Implementations are free to ignore such values for the maximum load factor
but they are not
required to.

I believe infinity should either become an invalid precondition for
`max_load_factor(z)` or the
wording around reserve() should be updated so as to guide implementations
how to handle
this value of maximum load factor.

- Christian

Received on 2022-09-13 16:59:10