unordered_map クラス

このテンプレート クラスは、std::pair<const Key, Ty> 型要素の可変長シーケンスを制御するオブジェクトを表します。このシーケンスは、ハッシュ関数によって、"バケット" と呼ばれる一列に並んだサブシーケンスに分割され、弱い順序付けがなされます。各バケット内では、比較関数によって要素間の大小関係が決定されます。各要素は、並べ替えキーと値という、2 つのオブジェクトを持ちます。このシーケンスは、すべてのバケットの長さがおおよそ等しければ、シーケンス内の要素数にかかわらず一定の演算回数 (定数時間) で、任意の要素を検索、挿入、削除できるような方法で表現されます。最悪のケースは、すべての要素が 1 つのバケットに集められたときです。演算の回数は、シーケンス内の要素数に比例して増えることになります (線形時間)。要素を挿入しても反復子の有効性は失われません。また、要素を削除した場合は、削除された要素を指す反復子だけが無効化されます。

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;

パラメーター

メンバー

解説

このオブジェクトは、このオブジェクトが制御するシーケンスを、格納されている 2 つのオブジェクト (unordered_map::key_equal 型の比較関数オブジェクトと、unordered_map::hasher 型のハッシュ関数オブジェクト) を呼び出すことによって並べ替えます。格納されている 1 つ目のオブジェクトには、メンバー関数 unordered_map::key_eq() を呼び出すことによってアクセスします。格納されている 2 つ目のオブジェクトには、メンバー関数 unordered_map::hash_function() を呼び出すことによってアクセスします。具体的には、Key 型のすべての値 X と Y について、key_eq()(X, Y) が呼び出され、2 つの引数値の大小関係が等しい場合は true が返されます。hash_function()(keyval) の呼び出しからは、size_t 型の値の分布が生成されます。unordered_multimap クラス テンプレート クラスとは異なり、unordered_map テンプレート クラスのオブジェクトでは、被制御シーケンスの任意の 2 つの要素間で key_eq()(X, Y) が常に false になることが保証されます。キーの重複は許されません。

このオブジェクトには、さらに、適切とされるバケットあたりの最大平均要素数を指定する最大テーブル占有率が格納されます。要素を挿入することによって unordered_map::load_factor() が最大テーブル占有率を超えるような場合、コンテナーは、バケット数を増やし、必要に応じて、ハッシュ テーブルを再構築します。

被制御シーケンスにおける要素の実際の順序は、ハッシュ関数、比較関数、挿入の順序、最大テーブル占有率、現在のバケット数などによって異なります。通常、被制御シーケンス内の要素の順序を予測することはできません。ただし、被制御シーケンス内で同じ大小関係を持った一連の要素は必ず隣接して存在します。

被制御シーケンスに対するストレージの割り当ておよび解放は、格納されている unordered_map::allocator_type 型のアロケーター オブジェクトを介して行われます。このアロケーター オブジェクトは、allocator テンプレート クラスのオブジェクトと同じ外部インターフェイスを持っている必要があります。コンテナー オブジェクトを代入しても、格納されているアロケーター オブジェクトはコピーされない点に注意してください。

必要条件

ヘッダー : <unordered_map>

名前空間: std

参照

関連項目

<unordered_map>

unordered_map クラス

その他の技術情報

<unordered_map> メンバー