c++unordered-mapstdbuckets

What bucket_count value should I use if I know the intended number of map keys?


I'm creating an std::unordered_map which I will immediately proceed to populate with n key-value pairs - and I know n. After that no more elements will be added - I will only be performing lookups.

What, therefore, should I pass as bucket_count to the constructor?

Notes:


Solution

  • According to n4296 in 23.5.4.2 [unord.map.cnstr] (this is the final draft of C++14) by default the max_load_factor for an unordered_map is 1.0, so you could just set the bucket_count to n.

    There is obviously a space-time trade-off between increasing the bucket count for improved speed and decreasing it (and raising the max load factor) for improved space.

    I would either not worry about it, or if it is a large map, set the bucket count to n. Then you can worry about optimizing when profiling shows you have a problem.

    If you know the range of load factors you want, then you just set the bucket count to std::ceil(n/(std::max(f_1,f_2)), (and set the load factor before you fill the map).