unordered_map クラス

[アーティクル]
06/09/2015

このテンプレートクラスは、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;

パラメーター

パラメーター	説明
Key	キーの型。
Ty	マップされた型。
Hash	ハッシュ関数のオブジェクト型。
Pred	等価比較関数のオブジェクト型。
Alloc	アロケータークラス。

メンバー

型定義	説明
unordered_map::allocator_type	ストレージを管理するためのアロケーターの型です。
unordered_map::const_iterator	被制御シーケンスの定数反復子の型です。
unordered_map::const_local_iterator	被制御シーケンスの定数バケット反復子の型です。
unordered_map::const_pointer	要素への定数ポインターの型です。
unordered_map::const_reference	要素への定数参照の型です。
unordered_map::difference_type	2 つの要素間の距離を表す、符号付きの型です。
unordered_map::hasher	ハッシュ関数の型です。
unordered_map::iterator	被制御シーケンスの反復子の型です。
unordered_map::key_equal	比較関数の型です。
unordered_map::key_type	順序付けキーの型です。
unordered_map::local_iterator	被制御シーケンスのバケット反復子の型です。
unordered_map::mapped_type	各キーに関連付けられた、マップされた値の型です。
unordered_map::pointer	要素へのポインターの型です。
unordered_map::reference	要素への参照の型です。
unordered_map::size_type	2 つの要素間の距離を表す、符号なしの型です。
unordered_map::value_type	要素の型。

メンバー関数	説明
unordered_map::at	指定したキーを持つ要素を検索します。
unordered_map::begin	被制御シーケンスの先頭を指定します。
unordered_map::bucket	キー値のバケット番号を取得します。
unordered_map::bucket_count	バケット数を取得します。
unordered_map::bucket_size	バケットのサイズを取得します。
unordered_map::cbegin	被制御シーケンスの先頭を指定します。
unordered_map::cend	被制御シーケンスの末尾を指定します。
unordered_map::clear	すべての要素を削除します。
unordered_map::count	指定したキーに一致する要素の数を検索します。
unordered_map::emplace	構築された要素を適切な場所に追加します。
unordered_map::emplace_hint	構築された要素を適切な場所にヒントと一緒に追加します。
unordered_map::empty	要素が存在しないかどうかをテストします。
unordered_map::end	被制御シーケンスの末尾を指定します。
unordered_map::equal_range	指定したキーに一致する範囲を検索します。
unordered_map::erase	指定した位置にある要素を削除します。
unordered_map::find	指定したキーに一致する要素を検索します。
unordered_map::get_allocator	格納されているアロケーターオブジェクトを取得します。
unordered_map::hash_function	格納されているハッシュ関数オブジェクトを取得します。
unordered_map::insert	要素を追加します。
unordered_map::key_eq	格納されている比較関数オブジェクトを取得します。
unordered_map::load_factor	バケットごとの平均要素数をカウントします。
unordered_map::max_bucket_count	最大バケット数を取得します。
unordered_map::max_load_factor	バケットあたりの最大要素数を取得または設定します。
unordered_map::max_size	被制御シーケンスの最大サイズを取得します。
unordered_map::rehash	ハッシュテーブルをリビルドします。
unordered_map::size	要素の数をカウントします。
unordered_map::swap	2 つのコンテナーのコンテンツを交換します。
unordered_map::unordered_map	コンテナーオブジェクトを構築します。

[演算子]	説明
unordered_map::operator[]	指定したキーを持つ要素を検索または挿入します。
unordered_map::operator=	ハッシュテーブルをコピーします。

解説

このオブジェクトは、このオブジェクトが制御するシーケンスを、格納されている 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 クラス

パラメーター

メンバー

解説

必要条件

参照

関連項目

概念

その他のリソース