Why does std::unordered_map have a reserve method?

Question

The unordered_map container has a reserve method because it is implemented using buckets, and not a tree as in map.

A bucket is:

a slot in the container’s internal hash table to which elements are assigned based on the hash value of their key. Buckets are numbered from 0 to (bucket_count-1). (source)

A single bucket holds a variable number of items. This number is based on the load_factor. When the load_factor reaches a certain threshold, the container increases the number of buckets and rehashes the map.

When you call reserve(n), the container creates enough buckets to hold at least n items.

This is in contrast to rehash(n) which directly sets the number of buckets to n and triggers a rebuild of the entire hash table.

See also: Pre-allocating buckets in a C++ unordered_map

Edit in Response to Comments

As I do not know the exact answer to the question posed in the comments, and as my preliminary research did not prove fruitful, I decided to test it experimentally.

For reference, the question boils down to:

Could you please explain if reserving buckets for n elements is the same as allocating memory for n elements?

According to this answer, accurately retrieving the size of the allocated space in an unordered_map is tricky and unreliable. So I decided to make use of Visual Studio 2015’s diagnostic tools.

First, my test case is as follows:

#include <unordered_map>
#include <cstdint>

struct Foo
{
    Foo() : x(0.0f), y(0.0f), z(0.0f) { }

    float x;
    float y;
    float z;
};

int32_t main(int32_t argc, char** argv)
{
    std::unordered_map<uint32_t, Foo> mapNoReserve;
    std::unordered_map<uint32_t, Foo> mapReserve;

    // --> Snapshot A

    mapReserve.reserve(1000);

    // --> Snapshot B

    for(uint32_t i = 0; i < 1000; ++i)
    {
        mapNoReserve.insert(std::make_pair(i, Foo()));
        mapReserve.insert(std::make_pair(i, Foo()));
    }

    // -> Snapshot C

    return 0;
}

Where the comments indicate, I took a memory snapshot.

The results were as follows:

Snapshot A:

┌──────────────┬──────────────┬──────────────┐
|     Map      | Size (Bytes) | Bucket Count |
|--------------|--------------|--------------|
| mapNoReserve | 64           | 8            |
| mapReserve   | 64           | 8            |
└──────────────┴──────────────┴──────────────┚

Snapshot B:

┌──────────────┬──────────────┬──────────────┐
|     Map      | Size (Bytes) | Bucket Count |
|--------------|--------------|--------------|
| mapNoReserve | 64           | 8            |
| mapReserve   | 8231         | 1024         |
└──────────────┴──────────────┴──────────────┚

Snapshot C:

┌──────────────┬──────────────┬──────────────┐
|     Map      | Size (Bytes) | Bucket Count |
|--------------|--------------|--------------|
| mapNoReserve | 24024        | 1024         |
| mapReserve   | 24024        | 1024         |
└──────────────┴──────────────┴──────────────┚

Interpretation:

As you can see from the snapshot, it appears that both maps grow in size once we start adding elements to them, even the one that had called reserve.

So does reserve offer a benefit even though memory is still allocated? I would say yes for two reasons: (1) It pre-allocates the memory for the buckets, and (2) it can prevent the need of a rehash, which as discussed earlier completely rebuilds the map.

Leave a Comment Cancel reply