Map

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

言語： Visual Basic C#

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

説明

Map は重複を許可しない連想配列コンテナです。任意の型をインデックスとしてシーケンスの要素にアクセスできるほか、ほとんどの操作を対数時間で行うことができます。

Mapの特徴
Mapの反復子
メソッド一覧

Mapの特徴

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

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

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

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

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

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

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

任意の型をインデックスとして使用できる

Map は連想配列コンテナです。要素はキーと値の２つをもち、キーの型は任意です。キーを指定してのアクセスを対数時間で実現します。例えば、キーが文字列で値が数値であるような場合には以下のように記述できます。

Dim cont = New Map(Of String, Integer)(New Less(Of String))
 
cont("sin") = 1989
cont("wish") = 1991
cont("closer") = 1994
cont("wretched") = 1999

var cont = new Map<string, int>( new Less<string>() );
 
cont["sin"] = 1989;
cont["wish"] = 1991;
cont["closer"] = 1994;
cont["wretched"] = 1999;

キーの重複を許さない

Map はキーの重複を許しません。上記の At のようなプロパティがサポートできるのはそのためです。MultiMap ではキーの重複が許されるため、At はサポートされません。また、要素の追加時にキーが「等順位」とみなされる要素が既にシーケンス内に存在した場合、要素の追加は失敗します。要素の重複を許したい場合は MultiMap を使用してください。

メモリの消費量が多い

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

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

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

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

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

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

ページトップへ

Mapの反復子

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

MapIterator ・・・ Begin および End が返す標準の反復子です。
MapRIterator ・・・ RBegin および REnd が返す逆方向反復子です。

ページトップへ

メソッド一覧

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

コンストラクタ

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

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

述語オブジェクト

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

参照・設定　

メソッド	説明
At	キーを指定してシーケンスの要素の値を取得／設定します

反復子

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

挿入・削除

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

サイズ

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

検索

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

置き換え

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

比較

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

Map

説明