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

Question

据this你不能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）。 （source）

单个桶容纳可变数量的项目。此编号基于load_factor。当load_factor达到某个阈值时，容器将增加桶的数量并重新映射该映射。

当您致电reserve(n)时，容器会创建足够的桶以容纳至少n项。

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

参见：Pre-allocating buckets in a C++ unordered_map

编辑回应评论

由于我不知道确切的答案，在意见中提出的问题，并作为我的初步研究没有证明是富有成果的，我决定通过实验测试它。

作为参考，这个问题归结为：

能否请您解释一下，如果保留水桶n个元素是相同的n个元素分配内存？

根据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; 
} 

凡评论表明，我参加了一个内存快照。

的结果如下：

快照答：

┌──────────────┬──────────────┬──────────────┐ 
|  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，这正如前面讨论的完全重建地图。