unordered_multiset クラス

更新 : 2007 年 11 月

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

template<class Key,
    class Hash = std::tr1::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key> >
    class unordered_multiset;

パラメータ

• Key
  キーの型。

• Hash
  ハッシュ関数のオブジェクト型。

• Pred
  等価比較関数のオブジェクト型。

• Alloc
  アロケータ クラス。

Members

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

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

解説

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

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

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

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

必要条件

ヘッダー : <unordered_set>

名前空間 : std::tr1

参照

参照

<unordered_set>

unordered_multiset クラス