c++ - 为什么 std::unordered_map 有保留方法？

Question

根据this你不能为 std::map:

保留空间

No, the members of the map are internally stored in a tree structure. There is no way to build the tree until you know the keys and values that are to be stored.

从这里很明显为什么 std::map 会缺少 reserve() 方法，它在 cppreference.com 上就是这样做的。但是， std::unordered_map does 有一个 reserve() 方法，但是当我尝试将它与 operator[]、insert() 或 emplace() 尽管我先调用了 reserve()，但它们都会分配内存。

这是怎么回事？为什么 reserve() 不能正确保留所需的空间？如果和map一样，你不能事先分配内存，那么为什么std::unordered_map甚至还有一个reserve()方法呢？

Answer 1

unordered_map 容器有一个 reserve 方法，因为它是使用存储桶实现的，而不是像 map 中的树。

一个桶是:

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)

单个存储桶包含可变数量的项目。此数字基于 load_factor .当 load_factor 达到某个阈值时，容器会增加桶数并重新散列 map 。

当您调用 reserve(n) 时，容器会创建足够的桶来容纳至少 n 个项目。

这与 rehash(n) 不同。它直接将桶数设置为 n 并触发整个哈希表的重建。

另请参阅:Pre-allocating buckets in a C++ unordered_map

根据评论进行编辑

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

作为引用，问题归结为:

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

根据this answer ，准确检索 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         |
└──────────────┴──────────────┴──────────────┚

解读:

正如您从快照中看到的那样，一旦我们开始向它们添加元素，这两个 map 的大小似乎都会增加，即使是调用了 reserve 的 map 也是如此。

那么，即使仍然分配了内存，reserve 也会带来好处吗？我会说是的，原因有两个:(1)它为存储桶预先分配内存，(2)它可以防止需要 rehash，如前所述，它可以完全重建 map 。