multiset クラス

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

標準テンプレートライブラリの multiset クラスは、コレクションのデータを格納および取得するために使用されます。コレクションに含まれる要素の値は一意である必要はなく、データが自動的に順序付けられるときにキー値として使用されます。 multiset 内の要素のキー値は直接変更できません。代わりに、以前の値を削除し、新しい値の要素を挿入する必要があります。

template < 
   class Key,  
   class Compare=less<Key>,  
   class Allocator=allocator<Key>  
> 
class multiset

パラメーター

Key
multiset に格納される要素のデータ型。
Compare
2 つの要素の値を並べ替えキーとして比較して、multiset 内の要素の相対順序を決定できる関数オブジェクトを提供する型。二項述語 less<Key> が既定値です。
Allocator
メモリの multiset の割り当てと解放に関する詳細をカプセル化する、格納されたアロケーターオブジェクトを表す型。既定値は allocator*<Key>* です。

解説

STL multiset クラスは、

連想コンテナーであり、関連付けられたキー値に基づいて要素の値を効率的に取得できるようにする可変サイズのコンテナーとして機能します。
反転することができます。これは、要素にアクセスするための双方向反復子が用意されているためです。
並べ替えが実行されます。これは、指定した比較関数に従ってコンテナー内のキー値によって要素に順序が設定されるためです。
複数対応です。要素は一意のキーを持つ必要がないので、関連する多くの要素値を 1 つのキー値が持つことができるためです。
単純な連想コンテナーです。これは、要素値がキー値であるためです。
テンプレートクラスとして機能します。これは、このクラスに用意されている機能が汎用的な機能であり、要素として保持されているデータの特定の型に依存しないためです。使用されているデータ型は、クラステンプレートで比較関数やアロケーターと共にパラメーターとして指定されます。

multiset クラスに用意されている反復子は双方向反復子ですが、クラスメンバー関数 insert と multiset には、弱い入力反復子をテンプレートパラメーターとして取得するバージョンがあります。この反復子の機能に関する要件は、双方向反復子のクラスで保証されている要件よりも低くなっています。これらの反復子の機能に差異があるのは、反復子の概念が異なっているためです。反復子の各概念には、反復子独自の一連の要件が含まれています。また、それらの要件を使用するアルゴリズムでは、反復子の種類ごとに指定されている要件に対して、前提を絞り込む必要があります。たとえば、一部のオブジェクトを参照するために入力反復子が逆参照される可能性があることを前提とする場合があります。さらに、シーケンス内にある次の反復子に対して逆参照が増加する可能性があることを前提とする場合もあります。このことは、最小限実施することですが、クラスのメンバー関数のコンテキストに含まれる反復子の範囲 [First, Last) について明確にすることも重要です。

一般的に、コンテナー型の選択は、アプリケーションにおいて必要な検索および挿入の種類に基づいている必要があります。連想コンテナーは、検索、挿入、削除の各操作用に最適化されています。これらの操作を明示的にサポートするメンバー関数は効率的であり、処理時間は平均的にコンテナー内にある要素の数の対数に比例します。要素を挿入しても反復子の有効性は失われません。また、要素を削除した場合は、削除された要素を具体的に指す反復子だけが無効化されます。

値とキーを関連付ける条件をアプリケーションが満たしている場合、multiset は最適な連想コンテナーとなっている必要があります。 multiset の要素は複数の場合があり、それ自体の並べ替えキーとして機能する場合があるため、キーは一意ではありません。この種類の構造体のモデルは、単語が複数回出現する可能性がある単語の順序付きのリストです。単語が複数回出現することが許可されてない場合は、set が適切なコンテナー構造体となります。一意の定義が値として一意のキーワードのリストにアタッチされている場合は、map がこのデータを格納するのに適切な構造体です。定義が一意でない場合は、multimap が最適なコンテナーです。

multiset では、Compare 型の格納されている関数オブジェクトを呼び出すことによって、制御するシーケンスを並べ替えます。格納されているこのオブジェクトは比較関数であり、メンバー関数 key_comp を呼び出すことによってアクセスできます。通常、要素は、この順序を確立するために小なり比較だけを実行できる必要があります。これにより、2 つの要素が指定されたときに、それらの要素が等しいか (どちらか一方が小さくはない)、または一方が他方より小さいかを判断できます。この結果、等価でない複数の要素間で順序が付けられます。テクニカルノートでは、比較関数は、数学上の標準的な意味で厳密弱順序を発生させる二項述語であると示されています。二項述語 f(x,y) は、2 つの引数オブジェクト (x および y) と戻り値 (true または false) を持つ関数オブジェクトです。 set に適用される順序付けは、二項述語が非再帰、反対称、推移的であり、等価性が推移的である (2 つのオブジェクト x と y が、f(x,y) と f(y,x) の両方が false の場合に等価になるように定義されている) 場合、厳密弱順序になります。 2 つのキーの等値に関する条件が等価性の条件よりも厳しく、優先される場合、順序付けは完全な順序付け (すべての要素が相互の値に基づいて並べ替えられる) となり、一致するそれぞれのキーを識別するのが難しくなります。

コンストラクター

multiset

空であるか、指定された multiset の全体または一部のコピーである multiset を構築します。

Typedef

allocator_type	multiset オブジェクトの allocator クラスの typedef。
const_iterator	multiset 内の const 要素を読み取ることができる双方向反復子の typedef。
const_pointer	multiset 内の const 要素へのポインターの typedef。
const_reference	multiset に格納された const 要素への参照の typedef (読み取りと const 操作を実行するため)。
const_reverse_iterator	multiset 内の const 要素を読み取ることができる双方向反復子の typedef。
difference_type	反復子が指す要素の範囲内にある multiset の要素の数に対する符号付き整数の typedef。
iterator	multiset 内の任意の要素の読み取りまたは変更ができる双方向反復子の typedef。
key_compare	2 つのキーを比較して、multiset 内の 2 つの要素の相対順序を決定できる関数オブジェクトの typedef。
key_type	2 つの並べ替えキーを比較して、multiset 内の 2 つの要素の相対順序を決定できる関数オブジェクトの typedef。
pointer	multiset 内の要素へのポインターの typedef。
参照	multiset に格納されている要素への参照の typedef。
reverse_iterator	反転された multiset 内の 1 つの要素の読み取りまたは変更ができる双方向反復子の typedef。
size_type	multiset 内の要素の数を表すことができる符号なし整数型。
value_compare	2 つ要素を並べ替えキーとして比較して、multiset 内の相対順序を決定できる関数オブジェクトの typedef。
value_type	要素としての値として、容量が multiset として格納されるオブジェクトを表す typedef。

メンバー関数

begin	multiset 内の最初の要素を指す反復子を返します。
cbegin	multiset 内の最初の要素を指す定数反復子を返します。
cend	multiset 内の最後の要素の次の位置を指す定数反復子を返します。
clear	multiset のすべての要素を消去します。
count	パラメーターに指定したキーに一致するキーを持つ、multiset 内の要素の数を返します。
crbegin	反転された set 内の最初の要素を指す定数反復子を返します。
crend	反転された set 内の最後の要素の次の位置を指す定数反復子を返します。
emplace	インプレースで構築された要素を multiset に挿入します。
emplace_hint	インプレースで構築された要素を、配置ヒントと共に multiset に挿入します。
empty	multiset が空かどうかをテストします。
End	multiset 内の最後の要素の次の位置を指す反復子を返します。
equal_range	反復子のペアを返します。ペアに含まれる最初の反復子は、指定したキーよりも大きいキーを持つ、multiset 内の最初の要素を指します。ペアに含まれる 2 番目の反復子は、指定したキー以上のキーを持つ、multiset 内の最初の要素を指します。
erase	multiset 内の要素または要素の範囲を指定した位置から削除するか、または指定したキーと一致する要素を削除します。
find	指定したキーと同じキーを持つ、multiset 内の要素の位置を指す反復子を返します。
get_allocator	multiset の構築に使用される allocator オブジェクトのコピーを返します。
insert	multiset に要素または要素範囲を挿入します。
key_comp	2 つの並べ替えキーを比較して、multiset 内の 2 つの要素の相対順序を決定できる関数オブジェクトを提供します。
lower_bound	指定したキー以上のキーを持つ、multiset 内の最初の要素を指す反復子を返します。
max_size	multiset の最大長を返します。
rbegin	反転された multiset 内の最初の要素を指す反復子を返します。
rend	反転された multiset 内の最後の要素の次の位置を指す反復子を返します。
size	multiset 内の要素数を返します。
swap	2 つの multiset の要素を交換します。
upper_bound	指定したキー以上のキーを持つ、multiset 内の最初の要素を指す反復子を返します。
value_comp	multiset 内の要素の値を並べ替えるために使用される比較オブジェクトのコピーを取得します。

演算子

operator=

別の multiset のコピーで multiset の要素を置き換えます。

必要条件

ヘッダー: <set>

名前空間: std

参照

概念

コンテナー

その他の技術情報

<set> メンバー

次の方法で共有