unordered_set クラス
このテンプレート クラスは、const Key 型要素の可変長シーケンスを制御するオブジェクトを表します。 このシーケンスは、ハッシュ関数によって、"バケット" と呼ばれる一列に並んだサブシーケンスに分割され、弱い順序付けがなされます。 各バケット内では、比較関数によって要素間の大小関係が決定されます。 各要素には、並べ替えキーと値という、2 つの側面があります。 このシーケンスは、すべてのバケットの長さがおおよそ等しければ、シーケンス内の要素数にかかわらず一定の演算回数 (定数時間) で、任意の要素を検索、挿入、削除できるような方法で表現されます。 最悪のケースは、すべての要素が 1 つのバケットに集められたときです。演算の回数は、シーケンス内の要素数に比例して増えることになります (線形時間)。 要素を挿入しても反復子の有効性は失われません。また、要素を削除した場合は、削除された要素を指す反復子だけが無効化されます。
template<class Key,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class unordered_set;
パラメーター
パラメーター |
説明 |
Key |
キーの型。 |
Hash |
ハッシュ関数のオブジェクト型。 |
Pred |
等価比較関数のオブジェクト型。 |
Alloc |
アロケーター クラス。 |
メンバー
型定義 |
説明 |
ストレージを管理するためのアロケーターの型です。 |
|
被制御シーケンスの定数反復子の型です。 |
|
被制御シーケンスの定数バケット反復子の型です。 |
|
要素への定数ポインターの型です。 |
|
要素への定数参照の型です。 |
|
2 つの要素間の距離を表す、符号付きの型です。 |
|
ハッシュ関数の型です。 |
|
被制御シーケンスの反復子の型です。 |
|
比較関数の型です。 |
|
順序付けキーの型です。 |
|
被制御シーケンスのバケット反復子の型です。 |
|
要素へのポインターの型です。 |
|
要素への参照の型です。 |
|
2 つの要素間の距離を表す、符号なしの型です。 |
|
要素の型。 |
メンバー関数 |
説明 |
被制御シーケンスの先頭を指定します。 |
|
キー値のバケット番号を取得します。 |
|
バケット数を取得します。 |
|
バケットのサイズを取得します。 |
|
被制御シーケンスの先頭を指定します。 |
|
被制御シーケンスの末尾を指定します。 |
|
すべての要素を削除します。 |
|
指定したキーに一致する要素の数を検索します。 |
|
構築された要素を適切な場所に追加します。 |
|
構築された要素を適切な場所にヒントと一緒に追加します。 |
|
要素が存在しないかどうかをテストします。 |
|
被制御シーケンスの末尾を指定します。 |
|
指定したキーに一致する範囲を検索します。 |
|
指定した位置にある要素を削除します。 |
|
指定したキーに一致する要素を検索します。 |
|
格納されているアロケーター オブジェクトを取得します。 |
|
格納されているハッシュ関数オブジェクトを取得します。 |
|
要素を追加します。 |
|
格納されている比較関数オブジェクトを取得します。 |
|
バケットごとの平均要素数をカウントします。 |
|
最大バケット数を取得します。 |
|
バケットあたりの最大要素数を取得または設定します。 |
|
被制御シーケンスの最大サイズを取得します。 |
|
ハッシュ テーブルをリビルドします。 |
|
要素の数をカウントします。 |
|
2 つのコンテナーのコンテンツを交換します。 |
|
コンテナー オブジェクトを構築します。 |
演算子 |
説明 |
ハッシュ テーブルをコピーします。 |
解説
このオブジェクトは、このオブジェクトが制御するシーケンスを、格納されている 2 つのオブジェクト (unordered_set::key_equal 型の比較関数オブジェクトと、unordered_set::hasher 型のハッシュ関数オブジェクト) を呼び出すことによって並べ替えます。 格納されている 1 つ目のオブジェクトには、メンバー関数 unordered_set::key_eq() を呼び出すことによってアクセスします。格納されている 2 つ目のオブジェクトには、メンバー関数 unordered_set::hash_function() を呼び出すことによってアクセスします。 具体的には、Key 型のすべての値 X と Y について、key_eq()(X, Y) が呼び出され、2 つの引数値の大小関係が等しい場合は true が返されます。hash_function()(keyval) の呼び出しからは、size_t 型の値の分布が生成されます。 unordered_multiset クラス テンプレート クラスとは異なり、unordered_set テンプレート クラスのオブジェクトでは、被制御シーケンスの任意の 2 つの要素間で key_eq()(X, Y) が常に false になることが保証されます。キーの重複は許されません。
このオブジェクトには、さらに、適切とされるバケットあたりの最大平均要素数を指定する最大テーブル占有率が格納されます。 要素を挿入することによって unordered_set::load_factor() が最大テーブル占有率を超えるような場合、コンテナーは、バケット数を増やし、必要に応じて、ハッシュ テーブルをリビルドします。
被制御シーケンスにおける要素の実際の順序は、ハッシュ関数、比較関数、挿入の順序、最大テーブル占有率、現在のバケット数などによって異なります。 通常、被制御シーケンス内の要素の順序を予測することはできません。 ただし、被制御シーケンス内で同じ大小関係を持った一連の要素は必ず隣接して存在します。
被制御シーケンスに対するストレージの割り当ておよび解放は、格納されている unordered_set::allocator_type 型のアロケーター オブジェクトを介して行われます。 このアロケーター オブジェクトは、allocator テンプレート クラスのオブジェクトと同じ外部インターフェイスを持っている必要があります。 コンテナー オブジェクトを代入しても、格納されているアロケーター オブジェクトはコピーされない点に注意してください。
必要条件
ヘッダー: <unordered_set>
名前空間: std