为什么 std::unordered_map 有一个保留方法？

根据this https://stackoverflow.com/questions/13049340/initializing-a-stdmap-when-the-size-is-known-in-advance您不能预留空间std::map:

不，映射的成员内部存储在树结构中。 除非您知道键和值，否则无法构建树 那些要被存储的。

由此可见为什么std::map会缺少一个reserve()方法，它在 cppreference.com 上执行。然而，std::unordered_map does have a reserve()方法，但是当我尝试使用它时operator[], insert() or emplace()尽管我已经打电话了，但他们都去分配内存reserve() first.

这是怎么回事？为什么不会reserve()正确保留所需空间？如果就像映射一样，您无法预先分配内存，那么为什么呢？std::unordered_map甚至有一个reserve()首先是方法？

The unordered_map容器有一个reserve方法，因为它是使用桶实现的，而不是像中那样使用树map.

一个桶是：

容器内部哈希表中的一个槽，根据其键的哈希值将元素分配到该槽。桶的编号从 0 到 (bucket_count-1)。 (source http://www.cplusplus.com/reference/unordered_map/unordered_map/bucket/)

单个桶可容纳数量可变的物品。这个数字是基于load_factor http://www.cplusplus.com/reference/unordered_map/unordered_map/load_factor/。当。。。的时候load_factor达到某个阈值，容器会增加桶的数量并重新散列映射。

你打电话时reserve(n) http://www.cplusplus.com/reference/unordered_map/unordered_map/reserve/，容器创建足够的桶来容纳至少n items.

这与rehash(n) http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/它直接将桶的数量设置为n并触发整个哈希表的重建。

也可以看看：在 C++ unordered_map 中预分配存储桶 https://stackoverflow.com/questions/5905204/pre-allocating-buckets-in-a-c-unordered-map

编辑回复评论

由于我不知道评论中提出的问题的确切答案，而且我的初步研究没有取得成果，所以我决定进行实验测试。

作为参考，问题归结为：

您能否解释一下为 n 个元素保留存储桶是否与为 n 个元素分配内存相同？

根据这个答案 https://stackoverflow.com/a/25438497/735425，准确检索分配空间的大小unordered_map是棘手且不可靠的。所以我决定使用 Visual Studio 2015 的诊断工具。

首先我的测试用例如下：

#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;
}

在评论指出的地方，我拍了一张内存快照。

结果如下：

快照A：

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

快照B：

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

快照C：

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

解释：

正如您从快照中看到的，一旦我们开始向其中添加元素，这两个映射的大小似乎都会增加，甚至是调用过的映射reserve.

So does reserve即使内存仍然分配也能带来好处？我会说是，有两个原因：（1）它为存储桶预先分配内存，（2）它可以防止需要rehash，如前所述，它完全重建了地图。