MultiSet
>> NGL >> リファレンス >> Containerカテゴリ >> Containerのクラス >> MultiSet
言語： Visual Basic C#
最終更新日付：2012/06/26 18:00:43
説明
MultiSet は重複を許可する集合コンテナです。ほとんどの操作を対数時間で行うことができます。
MultiSetの特徴
ここでは、MultiSet クラスの特徴について説明します。各コンテナの特徴を比較した表は「時間計算量について」をご覧下さい。
ほとんどの操作を対数時間で行える
MultiSet は、検索、挿入、削除といった操作を対数時間で実行します。ただし、ランダムアクセスコンテナではないため、n 番目の要素にアクセスするには先頭要素を指す反復子を n 回インクリメントする必要があります。
常に要素順でソートされる
MultiSet の内部は２分木構造になっています。要素は追加と同時にシーケンス内の適切な位置に挿入されるため、シーケンスは常に要素順でソートされた状態が保たれます。このような構造を維持しているため、上で紹介したような対数時間での操作が実現できるのです。
要素を順序付けるための述語を指定する
Set 同様、MultiSet はオブジェクトの作成時に、要素を順序付けるための述語オブジェクトを指定する必要があります。述語オブジェクトは「厳密な弱い順序付け」の規則に従っている必要があります。
Setと違い、要素の重複が許可される
MultiSet が Set と異なる点は、要素の重複が許可されることです。「等順位」となる要素が複数存在し得るため、要素を検索する場合は、LowerBound、UpperBound、EqualRange を使用します。
メモリの消費量が多い
MultiSet は NGL が提供するコンテナの中で最もメモリ消費量の多いコンテナのひとつです。基本的に Map/Set は同一のツリー構造をもちますが、キーと値の Pair オブジェクトを保有する点で Map と MultiMap の方がメモリをより多く消費します。
MultiSet は挿入、削除、検索といった領域で全体的に優秀な成績を上げますが、それぞれの領域のトップにはかないません。例えばランダムアクセスなら Vector や Deque にはかないませんし、挿入に関しては定数時間でこなす 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 | シーケンスの指定した位置に要素を１つ挿入します |
| 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.