今回は標準ライブラリ (Standard Template Library) の中から map の基本的な使い方を説明します。
一般に、キー (key) と値 (value) を関連付けて格納するデータ構造を「連想配列 (assocative array)」といいます。連想配列は多くのプログラミング言語でサポートされていて、プログラミング言語によっては、ハッシュ (hash), 辞書 (dictonary), マップ (map) などと呼ばれています。Ｃ++の場合、STL の map が連想配列で、実装には平衡二分木が使われています。スクリプト言語では連想配列の実装に「ハッシュ法」を用いることが多く、連想配列のことを「ハッシュ」と呼ぶようになりました。
map を使用するときは、ヘッダファイル map をインクルードしてください。変数の宣言は次のように行います。
map<キーのデータ型, 値のデータ型> 変数名;
map はテンプレートなので、< > の中にキーのデータ型と値のデータ型を指定してください。この場合、空 (要素数が 0) の連想配列が生成されます。キーの比較にはデフォルトで演算子 < が用いられます。キーを表すデータ型に bool operator<() が定義されていないとコンパイルエラーになります。ご注意くださいませ。
map のコンストラクタを下表に示します。
| 書式 | 機能 |
|---|---|
| map<K, V>(const map<K, V>& v) | コピーコンストラクタ |
| map<K, V>(s, e) | イテレータ s から e の手前までの要素を格納したマップを生成する |
コピーコンストラクタのほかにも代入演算子 = による map の代入も可能です。イテレータを使って map<K, V> を初期化する場合、その要素は構造体 pair<K, V> でなければいけません。また、最近の規格 (C++11) では、配列と同様に { ... } を使って map を初期化することができるようになりました。このときも要素は構造体 pair<K, V> になります。
要素のアクセスは添字演算子 [] で行うことができます。map は平衡二分木を使って実装されています。要素数を N とすると、map はデータの探索、挿入、削除を log2 N に比例する時間で実行することができます。拙作のページで作成した単純な二分探索木は、左右の部分木のバランスが崩れることがあるので、最悪の場合は N に比例する時間がかかります。平衡木は最悪の場合でも log2 N に比例する時間で実行することができます。
たとえば、マップが map<string, int> a と宣言されている場合、a["foo"] = 10 でマップ a のキー "foo" に 10 をセットすることができます。キーが存在しない場合は、マップにキーが登録されます。キーが存在する場合、キーに対応する値が書き換えられます。a["foo"] でキー "foo" の値を求めることができます。キーが存在しない場合、値のデフォルト値 V() が返されます。なお、キーの有無はメンバ関数 find() で判定することができます。これはあとで説明します。
それでは簡単な使用例を示しましょう。
リスト : map の簡単な使用例 (sample1909.cpp)
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
map<string, int> a;
a["foo"] = 1;
a["bar"] = 2;
a["baz"] = 3;
cout << a["foo"] << endl;
cout << a["oops"] << endl;
for (pair<string, int> x : a)
cout << "(" << x.first << "," << x.second << ")\n";
vector<pair<string, int>> b = {
{"Foo", 10}, {"Bar", 20}, {"Baz", 30}
};
map<string, int> c(b.begin(), b.end());
for (pair<string, int> x : c)
cout << "(" << x.first << "," << x.second << ")\n";
map<string, int> d = {
{"FOO", 10}, {"BAR", 20}, {"BAZ", 30}
};
for (pair<string, int> x : c)
cout << "(" << x.first << "," << x.second << ")\n";
}
構造体 pair のメンバ変数 (public) は first と second の 2 つがあります。map で pair を使用する場合、first にキーを、second に値をセットします。pair は構造体なので、{ ... } でメンバ変数を初期化することができます。map は範囲 for 文で要素を順番に取り出していくこともできます。プログラムは簡単なので説明は割愛します。実行結果は次のようになります。
$ clang++ sample1909.cpp $ ./a.out 1 0 (bar,2) (baz,3) (foo,1) (oops,0) (Bar,20) (Baz,30) (Foo,10) (Bar,20) (Baz,30) (Foo,10)
map は双方向イテレータをサポートしています。++ 演算子で次の要素に進み、-- 演算子で一つ前の要素に戻ることができます。イテレータを生成するメンバ関数を下表に示します。
| メンバ関数 | 機能 |
|---|---|
| begin() | 先頭要素を指し示すイテレータを返す |
| end() | 終端を指し示すイテレータを返す |
| cbegin() | 先頭要素を指し示す const イテレータを返す |
| cend() | 終端を指し示す const イテレータを返す |
| rbegin() | 先頭要素を指し示すリバースイテレータを返す |
| rend() | 終端を指し示すリバースイテレータを返す |
| crbegin() | 先頭要素を指し示す const リバースイテレータを返す |
| crend() | 終端を指し示す const リバースイテレータを返す |
const イテレータは要素を更新することができません。map の場合、先頭要素が一番小さなキー、末尾の要素が一番大きなキーになります。マップの要素をイテレータで順番に取り出すと、キーは昇順に出力されます。つまり、二分木を通りがけ順で巡回するわけです。リバースイテレータはその逆になります。
イテレータのデータ型は次のようになります。
map<K, V>::iterator // 通常のイテレータ map<K, V>::const_iterator // const イテレータ map<K, V>::reverse_iterator // リバースイテレータ map<K, V>::const_reverse_iterator // const リバースイテレータ
最近の規格 (C++11) を利用できるコンパイラでは auto を使ったほうが簡単でしょう。
簡単な使用例を示します。
リスト : イテレータの使用例 (sample1910.cpp)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> a = {
{"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}, {"hello", 5}
};
for (map<string, int>::const_iterator iter = a.cbegin(); iter != a.end(); ++iter)
cout << "(" << iter->first << "," << iter->second << ")\n";
for (auto iter = a.begin(); iter != a.end(); ++iter)
iter->second *= 10;
for (auto iter = a.rbegin(); iter != a.rend(); ++iter)
cout << "(" << iter->first << "," << iter->second << ")\n";
}
$ clang++ sample1910.cpp $ ./a.out (bar,2) (baz,3) (foo,1) (hello,5) (oops,4) (oops,40) (hello,50) (foo,10) (baz,30) (bar,20)
イテレータが指し示す要素のデータ型は pair<const K, V> です。値は書き換えることができますが、キーは参照することしかできません。
map は添字演算子 [] でキーの有無をチェックすることはできません。この場合、メンバ関数 find() を使います。find() はキーを見つけたらそれを指し示すイテレータを返します。見つからない場合は終端を指し示すイテレータを返します。
簡単な使用例を示します。
リスト : find の使用例 (sample1911.cpp)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> a = {
{"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}, {"hello", 5}
};
auto iter = a.find("baz");
if (iter != a.end()) {
cout << iter->second << endl;
} else{
cout << "not found\n";
}
iter = a.find("world");
if (iter != a.end()) {
cout << iter->second << endl;
} else{
cout << "not found\n";
}
}
$ clang++ sample1911.cpp $ ./a.out 3 not found
このほかにも、マップの最初の要素 (最小値) を求めるメンバ関数 lower_bound() や最後の要素 (最大値) を求める upper_bound() があります。これらの関数の返り値は find() と同じです。
データの挿入はメンバ関数 insert() でも行うことができます。引数のデータ型は pair<K, V> で、返り値のデータ型は pair<iterator, bool> です。実際にデータを挿入した場合、bool は true になります。同じキーが存在している場合、値は書き換えられずに、bool は false になります。iterator は要素へのイテレータです。
簡単な例を示しましょう。
リスト : insert の使用例 (sample1912.cpp)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> a = {
{"foo", 1}, {"bar", 2}, {"baz", 3}
};
auto r = a.insert(pair<string, int>("oops", 4));
cout << r.second << endl;
r = a.insert(pair<string, int>("foo", 10));
cout << r.second << endl;
for (auto p : a)
cout << "(" << p.first << "," << p.second << ")\n";
}
$ clang++ sample1912.cpp $ ./a.out 1 0 (bar,2) (baz,3) (foo,1) (oops,4)
データの削除はメンバ関数 erase() で行います。引数はキーで返り値は削除した要素の個数です。map の場合、キーと値の組は一つしかないので、要素を削除したら 1 を返し、キーが見つからない場合は 0 を返します。
簡単な使用例を示します。
リスト : erase の使用例 (sample1913.cpp)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> a = {
{"foo", 1}, {"bar", 2}, {"baz", 3}
};
string key[] = {
"oops", "foo", "bar", "baz"
};
for (string k : key) {
cout << a.erase(k) << endl;
cout << a.size() << endl;
}
cout << a.empty() << endl;
}
$ clang++ sample1913.cpp $ ./a.out 0 3 1 2 1 1 1 0 1
メンバ関数 size() は map の要素数を返します。empty() は map が空であれば true を、そうでなければ false を返します。また、map を空にするメンバ関数 clear() も用意されています。
キーの比較関数はテンプレートの第 3 引数で指定することができます。たとえば、比較関数 greater<string> を渡すと、キーを取り出すときは降順になります。簡単な使用例を示します。
リスト : 比較関数を指定する (sample1914.cpp)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> a = {
{"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}
};
for (auto p : a)
cout << p.first << endl;
map<string, int, greater<string>> b = {
{"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}
};
for (auto p : b)
cout << p.first << endl;
}
$ clang++ sample1914.cpp $ ./a.out bar baz foo oops oops foo baz bar
このほかにも便利なメンバ関数がありますし、algorithm の関数で map に適用できるものもあります。興味のある方は標準ライブラリのリファレンスをお読みくださいませ。