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

根据this，您不能为std::map保留空间:



由此可见，为什么std::map缺少cppreference.com上的reserve()方法。但是，std::unordered_map确实具有reserve()方法，但是当我尝试将其与operator[]，insert()或emplace()结合使用时，尽管我先调用了reserve()，但它们都会去分配内存。

这是怎么回事？为什么reserve()无法正确保留所需的空间？而且，如果与映射一样，您无法事先分配内存，那为什么std::unordered_map甚至首先要使用reserve()方法？

最佳答案

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

一个水桶是:



一个存储桶可容纳可变数量的项目。该数字基于 load_factor 。当load_factor达到某个阈值时，容器会增加存储桶的数量并重新映射。

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

这与 rehash(n) 相反，后者直接将存储桶数设置为n并触发整个哈希表的重建。

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

编辑以回复评论

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

供引用，问题归结为:



根据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         |
└──────────────┴──────────────┴──────────────┚

释义:

从快照中可以看到，一旦我们开始向其中添加元素，即使是称为reserve的 map ，两个 map 的大小都会增加。

那么即使仍然分配了内存，reserve也会带来好处吗？我会说是，原因有两个:(1)它为存储桶预先分配了内存，并且(2)它可以避免需要rehash，正如前面所讨论的，它可以完全重建映射。

关于c++ - 为什么std::unordered_map具有保留方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42373232/