なぜstd :: unordered_mapに予約メソッドがありますか？

Question

thisによると、あなたはstd::mapのためのスペースを確保することはできません。

いいえ、マップのメンバーは、内部ツリー構造に格納されています。 格納されるキーと値 がわかるまで、ツリーを構築する方法はありません。このことから

std::mapはそれがcppreference.comにしreserve()方法を、不足する理由は明白です。しかし、std::unordered_mapないはreserve()方法がありますが、私はoperator[]、insert()またはemplace()でそれを使用しようとすると、彼らはすべてのreserve()最初に呼び出さた私にもかかわらず、メモリを割り当てるために行きます。

これは何ですか？ reserve()が必要なスペースを適切に予約していないのはなぜですか？マップと同じように事前にメモリを割り当てることができない場合は、std::unordered_mapはなぜ最初にreserve()メソッドを持っていますか？

Answer 1

unordered_mapコンテナは、mapのようなツリーではなく、バケットを使用して実装されているため、reserveメソッドがあります。

バケットがある：

要素は、そのキーのハッシュ値に基づいて割り当てられているコンテナの内部ハッシュテーブルのスロット。バケットには0から（bucket_count-1）までの番号が付けられます。 （source）

単一のバケットは、可変数の項目を保持します。この数値はload_factorに基づいています。 load_factorが一定のしきい値に達すると、コンテナはバケットの数を増やしてマップを再ハッシュします。

reserve(n)を呼び出すと、コンテナは少なくともnのアイテムを保持するのに十分なバケットを作成します。

これは、nに直接バケット数を設定し、ハッシュテーブル全体の再構築をトリガーするrehash(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; 
} 

コメントが示す

が、私はメモリのスナップショットを取りました。

結果は以下の通りであった：

スナップショット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呼ばれていたとしても1に要素を追加し始めると、両方のマップのサイズが大きくなることが表示されます。

reserveはまだメモリが割り当てられていても利点がありますか？ （1）バケットのメモリをあらかじめ割り当てておき、（2）rehashの必要性を防ぐことができます。これは前述のように完全にマップを再構築します。