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

Question

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

31

根据此处的说明，您无法为std::map预留空间：

不行，映射的成员在内部以树结构存储。在知道要存储的键和值之前，没有办法构建树。

由此可以看出，std::map为什么缺少reserve()方法，在cppreference.com上也有说明。然而，std::unordered_map却有一个reserve()方法。但是，当我尝试将它与operator[]、insert()或emplace()一起使用时，它们都会去分配内存，尽管我已经先调用了reserve()。

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

- Mikubyte

你能描述一下你用的方法是如何确定 operator[]、insert() 或 emplace() 分配内存而不是使用预留的内存吗？ - nos

1

@nos 我在每个调用中逐步执行汇编代码，它们最终都会进入某种形式的 List_buy() 或 BuyNode() 调用，最终调用了 operator new() 和 malloc()。 - Mikubyte

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ssell · Accepted Answer

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

一个桶是:

容器内部哈希表中的一个槽，元素被分配到其中基于键的哈希值。桶从0到(bucket_count-1)进行编号。 (source)

单个桶可以容纳可变数量的项目。这个数字基于load_factor。当load_factor达到一定阈值时，容器会增加桶的数量并重新哈希映射。

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

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

另请参见：C++ unordered_map中预分配桶空间

根据评论编辑

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

参考文献，问题归结为：

请解释一下为什么为n个元素保留桶与为n个元素分配内存是相同的。

根据这个回答，准确检索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的那一个。

那么，reserve是否提供了好处，即使仍然分配了内存？我认为有两个原因：(1)它为桶预先分配内存，(2)它可以防止需要rehash，如前所述完全重建地图。