MultiMap

MultiMap

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

言語: Visual Basic    C#

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

説明

MultiMap は重複を許可する連想配列コンテナです。キーと値からなる任意の型のペアを要素とするツリー構造を管理し、ほとんどの操作を対数時間で行うことができます。

 

MultiMapの特徴

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

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

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

常にキー順でソートされる

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

キーを順序付けるための述語を指定する

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

Mapと違い、キーの重複が許可される

MultiMapMap と異なる点は、キーの重複が許可されることです。その結果、キーを指定しても対象が複数存在しうるため、At プロパティはサポートされません。キーを指定してデータを取り出す場合は、LowerBoundUpperBoundEqualRange を使用します。

メモリの消費量が多い

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

 

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

 

IEnumerable(Of Pair(Of K, V)) をサポート

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

IEnumerable<Pair<K, V>> をサポート

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

ページトップへ

 

MultiMapの反復子

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

ページトップへ

 

メソッド一覧

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

コンストラクタ

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

述語オブジェクト

メソッド 説明
KeyComp キーを順序付けるための述語オブジェクトを取得します
ValueComp キーと値の Pairを比較するための述語オブジェクトを取得します。

反復子

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

挿入・削除

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

サイズ

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

検索

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

置き換え

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

比較

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

 

 


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