Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の8_A問題をC++で解いてみました。
ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#8では、辞書（map コンテナ）を学びます。
問題（8_A: Map: Search）
問題はリンク先をご覧ください。
Map コンテナについて学びます。
Map コンテナについて
以下は、cpprefjp 様の記事を参考にさせていただきました。
概略
Map コンテナは、いわゆる連想配列を提供します。
- [key] によりキーが key である値にアクセスできる。
- コンテナの要素は、キーとその値の pair 型になる。
- 内部の要素は、小さいものから大きなものへとソートされる。
- キーに対応する値は、ユニークになる（複数の値を持たない）。
主なメソッド
よく使われるメソッドを紹介します。
| 名前 | 説明 |
| [] | 要素を取得する |
| insert | 要素を挿入する。 |
| erase | 要素を削除する。 |
| size | 要素数を返す。 |
| empty | コンテナが空なら true を、そうでなければ false を返す。 |
| clear | すべての要素を削除する。 |
| find | 指定したキーで要素を探す |
| count | 指定したキーにマッチする要素の数を返す。 |
| equal_range | 指定したキーにマッチする要素範囲を返す。 |
| lower_bound | 与えられた値より小さくない最初の要素へのイテレータを返す。 |
| upper_bound | 特定の値よりも大きい最初の要素へのイテレータを返す。 |
Mapコンテナは、二分木を使って実装されるため、insert はコンテナのサイズの対数時間（log）で、erase は定数時間で処理できます。指定したキーの値の様子を得る、[] もコンテナサイズの対数時間（log）で処理できます。
上記に加えて、二分探索で値を探索できる lower_bound（または upper_bound）も使うことができます。この機能は、8_C で解説します。
C++ プログラム例（ITP2 8_A）
問題で与えられるクエリに従い、キーを文字列とする辞書 M に対して、以下の操作を行います。
- クエリ0 キーが key で値が x である要素をコンテナ M に挿入する。キーが key である要素がすでに存在している場合は、要素の値を x に更新する。
- クエリ1 キーが key である値を出力する。
どちらのクエリも [] により実現できます。添え字で表現できているため、プログラムとして自然な表記になっています（20、24行目）。以下が、C++プログラムとなります。
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> M;
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 0) {
string key;
int x;
cin >> key >> x;
M[key] = x;
} else if (command == 1) {
string key;
cin >> key;
cout << M[key] << endl;
}
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
Map（連想配列） は、応用の範囲が広く、競技プログラミングでもよく使われています。トピック#8を通じて、map コンテナについて理解を深めたいと思います。
引き続き、ITP2 の問題を紹介していきます。
