MultiSet

MultiSet

 >> NGL >> リファレンス >> Containerカテゴリ >> Containerのクラス >> MultiSet

言語: Visual Basic    C#

最終更新日付:2012/06/26 18:00:43

説明

MultiSet は重複を許可する集合コンテナです。ほとんどの操作を対数時間で行うことができます。

 

MultiSetの特徴

ここでは、MultiSet クラスの特徴について説明します。各コンテナの特徴を比較した表は「時間計算量について」をご覧下さい。

ほとんどの操作を対数時間で行える

MultiSet は、検索、挿入、削除といった操作を対数時間で実行します。ただし、ランダムアクセスコンテナではないため、n 番目の要素にアクセスするには先頭要素を指す反復子を n 回インクリメントする必要があります。

常に要素順でソートされる

MultiSet の内部は2分木構造になっています。要素は追加と同時にシーケンス内の適切な位置に挿入されるため、シーケンスは常に要素順でソートされた状態が保たれます。このような構造を維持しているため、上で紹介したような対数時間での操作が実現できるのです。

要素を順序付けるための述語を指定する

Set 同様、MultiSet はオブジェクトの作成時に、要素を順序付けるための述語オブジェクトを指定する必要があります。述語オブジェクトは「厳密な弱い順序付け」の規則に従っている必要があります。

Setと違い、要素の重複が許可される

MultiSetSet と異なる点は、要素の重複が許可されることです。「等順位」となる要素が複数存在し得るため、要素を検索する場合は、LowerBoundUpperBoundEqualRange を使用します。

メモリの消費量が多い

MultiSet は NGL が提供するコンテナの中で最もメモリ消費量の多いコンテナのひとつです。基本的に Map/Set は同一のツリー構造をもちますが、キーと値の Pair オブジェクトを保有する点で MapMultiMap の方がメモリをより多く消費します。

 

MultiSet は挿入、削除、検索といった領域で全体的に優秀な成績を上げますが、それぞれの領域のトップにはかないません。例えばランダムアクセスなら VectorDeque にはかないませんし、挿入に関しては定数時間でこなす List には負けてしまいます。しかし、MultiSet には、シーケンスが常にソートされているという利点があります。

 

IEnumerable(Of T) をサポート

MultiSet は IEnumerable(Of T) インターフェースを実装しています(ここで、T はコンテナが格納する要素の型です)。そのため、For Each 構文を利用して要素の反復を行うことができます。

IEnumerable<T> をサポート

MultiSet は IEnumerable<T> インターフェースを実装しています(ここで、T はコンテナが格納する要素の型です)。そのため、foreach 構文を利用して要素の反復を行うことができます。

ページトップへ

 

MultiSetの反復子

MultiSet クラスは双方向反復子をサポートします。MultiSet が提供する反復子は Set のものと共通になっています。双方向反復子に関する詳細は BidirectionalIterator を参照してください。

ページトップへ

 

メソッド一覧

MultiSet クラスのメソッドの一覧を以下に示します。各コンテナがサポートするメソッドの一覧は「コンテナのメソッド」 をご覧下さい。

コンストラクタ

メソッド 説明
New いくつかの方法でコンテナオブジェクトを作成します。
メソッド 説明
MultiSet いくつかの方法でコンテナオブジェクトを作成します。

述語オブジェクト

メソッド 説明
KeyComp 要素を順序付けるための述語オブジェクトを取得します
ValueComp KeyCompメソッドと同じです。

反復子

メソッド 説明
Begin シーケンスの先頭を指す反復子を返します
End シーケンスの終端を指す反復子を返します
RBegin 逆シーケンスの先頭を指す逆方向反復子を返します
REnd 逆シーケンスの末尾を指す逆方向反復子を返します

挿入・削除

メソッド 説明
Insert シーケンスの指定した位置に要素を1つ挿入します
Erase シーケンスの指定した位置から要素を取り除きます
Clear シーケンス内の要素を全て取り除きます

サイズ

メソッド 説明
Empty 空シーケンスかどうかを返します
Size シーケンスが管理する要素の個数を返します
MaxSize 管理可能な要素の最大数を返します

検索

メソッド 説明
Find 指定したキーを持つ最初の要素を検索します
Count 指定したキーを持つ要素の数を返します
LowerBound 指定したキーよりも小さくない最小の要素を検索します
UpperBound 指定したキーよりも大きな最小の要素を検索します
EqualRange 指定したキーと一致する要素の範囲を検索します

置き換え

メソッド 説明
Swap 別の MultiSet オブジェクトと管理シーケンスを交換します

比較

メソッド 説明
IsEqual 他の MultiSet オブジェクトと等しいかどうか調べます。
Compare 他の MultiSet オブジェクトと辞書順比較をします。

 

 


Copyright(C) 2011-2012 Show MATSUOKA.
Powered by Prefab.