目次

map, multimapとは

Perlを勉強したことある人ならmapは連想配列に似ていると言えば分かると思います。

連想配列とはキーと値の組み合わせを記憶しておくものです。

普通の配列では、

phoneNumber[0] = "06-633-****";
phoneNumber[1] = "079-341-****";
phoneNumber[2] = "078-852-****";

というように添字には整数値しか使えません。

一方、連想配列では(C言語風に書くと)

char name[] = "山田";
phoneNumber[name] = "06-633-****";
phoneNumber["田中"] = "079-341-****";
phoneNumber["鈴木"] = "078-852-****";

と言うように数値以外の添字を使うことができます。 このような添字のことをキーと言います。

map, multimapはこの連想配列のようにキーと値をペアにして記憶します。 名前で検索して値を調べるという操作は辞書を引くことに似ています。 そのため、mapはDictionary(辞書)とも呼ばれています。 mapはキーの重複が許されず、multimapはキーの重複が許されます。

STLでは、キーと値を組にするためにpairというクラスが用意されています。

pair<Key, Value> //Keyという型とValueという型を組にした型

そしてmapやmultimapはこのpair型を要素とする2分探索木で実装されています。

mapにはoperator[]が用意されていて、 連想配列と同じように操作することができます。例をあげると、

map<string, string> phoneNumber;
phoneNumber["山田"] = "06-633-****";

と言うような操作ができます。

STLで2分探索木はxtreeというヘッダーファイル中にtreeという名前のクラスとして用意されています。 このtreeというクラスはset,multiset,map,multimapを実装するために用意されたクラスです。 したがってユーザーが直接このクラスを使う必要はありません。

mapの特徴

  • 要素の追加、キーによる検索、削除が O(log n) で行える

  • キーの重複を許さない

  • キーの値の小さな要素から順にアクセスできる

  • operator[]を用いてPerlの連想配列のように値にアクセスできる

multimapの特徴

  • 要素の追加、キーによる検索、削除が O(log n) で行える

  • キーの重複を許す

  • キーの値の小さな要素から順にアクセスできる

更新履歴

ブログ