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

Question

根据这个你不能为std::map以下空间预留空间:

不,地图的成员内部存储在树结构中.在知道要存储的键和值之前,无法构建树.

从这一点可以明显看出为什么std::map缺少一种reserve()方法,它在cppreference.com上做了.但是,std::unordered_map 确实有一个reserve()方法,但是当我尝试使用它时operator[],insert()或者emplace()尽管我reserve()先调用它们,它们都会分配内存.

怎么了？为什么不能reserve()妥善保留所需的空间？如果它与地图一样,你不能事先分配内存,那为什么std::unordered_map甚至首先有一个reserve()方法呢？

Answer 1

该unordered_map容器有一个reserve,因为它是在用桶来实现,而不是一棵树方法map.

一个桶是:

容器内部哈希表中的一个槽,根据键的哈希值为其分配元素.存储桶的编号从0到(bucket_count-1).(来源)

单个存储桶包含可变数量的项目.这个数字是基于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)它可以防止需要a rehash,如前所述完全重建地图.