c++ unordered_map is there a way to pre-allocate memory for elements if max size known in advance

Question

Looks like reserve/rehash functions only pre-allocate the number of buckets, not memory for the elements(key,vlaue) pairs to be inserted.

Is there a way we can pre-allocate memory for elements also, so low-latency apps dont need to waste time on dynamic memory allocation.

Answer 1

One possibility would be to write your own allocator. This can be especially effective if you have at least a fair idea of how many items are likely to go in the table (so you can pre-allocate space for all of them) and don't care about re-using space for items if they're removed from the table (so your bookkeeping is simple).

In such a case, you can basically pre-allocate space for N objects, and simply keep track of the position of the next item to be allocated. Allocating the object consists of simply returning the address and incrementing the pointer, as in return *next++;

Of course, this doesn't truly eliminate the dynamic allocation--it just makes it cheap enough that you probably don't care about it any more (and since it's supplied as a template parameter, there's a good chance of its being expanded inline, so you don't even get the overhead of a function call in the process.

Even if you can't put up with quite that restrictive of an allocator, a general-purpose allocator for fixed-size objects will still usually be (at least somewhat) faster than one for variable sizes of objects. It still won't eliminate the dynamic allocation, but it may give enough improvement in speed to work quite a bit better for your purpose.