爲什麼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，這正如前面討論的完全重建地圖。