When I call reserve(n) on a libc++'s empty unordered_set, libc++ find the next prime number as bucket_count if n is not a power of two, otherwise they just use n. This also makes reserve(15) have a bigger bucket_count than reserve(16).
if (__n == 1)
__n = 2;
else if (__n & (__n - 1))
__n = __next_prime(__n);
I am wondering is there any useful case of this?
I known that some hash-table implementation can use a power of two as size to avoid modulo calculations. But that seems make sense only if it is known at compile-time that only power-of-two numbers can be used.
Testing Demo: https://godbolt.org/z/W5joovP4q
#include <cstdio>
#include <unordered_set>
bool is_prime(int x) {
if (x < 2) return false;
if (x % 2 == 0) return x == 2;
for (int i = 3; i * i <= x; i += 2)
if (x % i == 0) return false;
return true;
}
int next_prime(int x) {
while (!is_prime(x))++x;
return x;
}
__attribute__((noinline))
void test(int i) {
std::unordered_set<char> s;
s.reserve(i);
int a = s.bucket_count();
int b = next_prime(i);
if (a != b) {
printf("%6d %6d %6d\n", i, a, b);
}
}
int main() {
for (int i = 0; i < 3000; ++i)
test(i);
}
Program stdout:
0 0 2
4 4 5
8 8 11
16 16 17
32 32 37
64 64 67
128 128 131
256 256 257
512 512 521
1024 1024 1031
2048 2048 2053