26

I'm using the std::unordered_map from gnu++0x to store a huge amount of data. I want to pre-allocate space for the large number of elements, since I can bound the total space used.

What I would like to be able to do is call:

std::unordered_map m;
m.resize(pow(2,x));

where x is known.

std::unordered_map doesn't support this. I would rather use std::unordered_map if possible, since it will eventually be part of the standard.

Some other constraints:

Need reliable O(1) access and mutation of the map. The desired hash and comparison functions are already non-standard and somewhat expensive. O(log n) mutation (as with std::map) is too expensive.

-> The expensive hash and comparison also make amortization-based growth way too expensive. Each extra insert requires O(n) operations from those functions, which results in an extra quadratic term in the algorithm's run time, since the exponential storage requirements need O(n) growths.

JFMR
  • 23,265
  • 4
  • 52
  • 76
JAD
  • 263
  • 1
  • 3
  • 4

5 Answers5

34
m.rehash(pow(2,x));

if pow(2, x) is the number of buckets you want preallocated. You can also:

m.reserve(pow(2,x));

but now pow(2, x) is the number of elements you are planning on inserting. Both functions do nothing but preallocate buckets. They don't insert any elements. And they are both meant to be used exactly for your use case.

Note: You aren't guaranteed to get exactly pow(2, x) buckets. Some implementations will use only a number of buckets which is a power of 2. Other implementations will use only a prime number of buckets. Still others will use only a subset of primes for the number of buckets. But in any case, the implementation should accept your hint at the number of buckets you desire, and then internally round up to its next acceptable number of buckets.

Here is the precise wording that the latest (N4660) uses to specify the argument to rehash:

a.rehash(n) : Postconditions: a.bucket_count() >= a.size() / a.max_load_factor() and a.bucket_count() >= n.

This postcondition ensures that bucket()_count() >= n, and that load_factor() remains less than or equal to max_load_factor().

Subsequently reserve(n) is defined in terms of rehash(n):

a.reserve(n) : Same as a.rehash(ceil(n / a.max_load_factor())).

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
4

I don't think it matters for an unordered map to have pre-allocated memory. The STL is expected to be O(n) amortized insertion time. Save yourself the hassle of writing your own allocator until you know this is the bottle neck of your code, in my opinion.

Mike Lyons
  • 22,575
  • 2
  • 16
  • 19
  • 2
    The STL guarantees O(n) amortized insertion time, but a common way of implementing this is to increase the number of buckets by a constant factor, and then rehash each existing element. This happens O(log n) times if you're storing n elements in the map. When n is 2^large, this adds an extra factor of large to the number of insertions performed. I'm trying to shave off this factor. – JAD May 11 '11 at 19:01
  • "this adds an extra factor of large" No, it adds an extra factor of 2. Do you understand how amortized operations work? The only real reason this answer is wrong is because it doesnt "guarantee" O(n) amortized insertion time, it only provides expected O(n) amortized insertion time, with exponentially high probability over randomly-inserted elements. If you know the exact sizes that the buckets will adjust to and the hash function that will be used, it's still possible to trick the hash table and force N collisions for every insertion. – codetaku Aug 14 '15 at 15:58
  • unless you're trying to do something that doesn't allocate - for example in a real time thread. in which case it matters. – UKMonkey Sep 02 '20 at 11:01
3

I would suggest writing your own allocator for the std::unordered_map that allocates memory exactly in the way you want.

orlp
  • 112,504
  • 36
  • 218
  • 315
1

The constructor takes a parameter "size_type bucket_count" according to http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

so the simplest way to do what your example code says is:

std::unordered_map m{ pow(2,x) };

This will be more efficient since it's undefined how many buckets will be reserved on construction otherwise, it may have to allocate and then deallocate when you call reserve afterwards.

Ben
  • 843
  • 8
  • 9
-2

I think rehash and reserve both work only if you know in advance how much memory your mapped value will take. If the mapped value is complicated or dynamically changes in size (e.g. a vector), you will need your own implementation. For example, if your memory size allows, you may reserve the biggest container that may ever happen to exist.

hrrl
  • 1
  • 1
  • 1
    Some points you make don't make sense, or you didn't make yourself understood. For instance "if the mapped value dynamically changes is size (e.g. vector)". No matter how many elements you have in a vector (or any container or class for that matter), `sizeof(std::vector)` remains the same (for the same `T` obviously). The `map` will reserve the exact amount of space for a `std::vector` of 1 element or a `std::vector` of 1 mil elements. "you may reserve the biggest container that may ever happen to exist" is another point that I don't view as a sound advice in the context of this question. – bolov Jan 14 '16 at 21:30