AOJ ITP2 8_D（Multi-Map）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の8_D問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#8では、辞書（map コンテナ）を学びます。

問題（8_D: Multi-Map）

問題はリンク先をご覧ください。

AOJ ITP2 8_D問題: Multi-Map

Mulitmap コンテナについて学びます。

Multimap コンテナについて

以下は、cpprefjp 様の記事を参考にさせていただきました。

概略

Multimap コンテナは、いわゆる連想配列を提供します。

• コンテナの要素は、キーとその値の pair 型になる。
• 内部の要素は、小さいものから大きなものへとソートされる。
• キーに対応する値は、重複を許す。

主なメソッド

よく使われるメソッドを紹介します。

Multimapコンテナは、二分木を使って実装されるため、insert はコンテナのサイズの対数時間（log）で、erase は定数時間で処理できます。ただし、map と異なり [] を使ったアクセスができません。

Map コンテナと同じく、二分探索で値を探索できる lower_bound（または upper_bound）も使うことができます。

C++ プログラム例（ITP2 8_D）

問題で与えられるクエリに従い、キーを文字列とする辞書 M に対して、以下の操作を行います。Multiset は、[] によるアクセスができないため、8_C と比較して宣言以外の行も変更されています。

• クエリ0　キーが key で値が x である要素をコンテナ M に挿入する。キーが key である要素がすでに存在している場合は、要素の値を x に更新する。
• クエリ1　キーが key である値をすべて出力する。
• クエリ2　キーが key であるすべての要素をコンテナ M から削除する。
• クエリ3　キーが辞書式順で L 以上、R 以下のキーと値の組順番に出力する。

Multimap コンテナで提供されているメソッドを、クエリに従い呼び出します。一部の型宣言は、長くなりすぎるため、auto を使いました（25、37、38行目）。

#include <iostream>
#include <map>

using namespace std;

int main()
{
	multimap<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.insert(make_pair(key, x));
		} else if (command == 1) {
			string key;
			cin >> key;
			if (M.count(key) > 0) {
				auto p = M.equal_range(key);
				for (auto it = p.first; it != p.second; ++it) {
					cout << it->second << endl;
				}
			}
		} else if (command == 2) {
			string key;
			cin >> key;
			M.erase(key);
		} else if (command == 3) {
			string L, R;
			cin >> L >> R;
			auto it = M.lower_bound(L);
			auto last = M.upper_bound(R);
			while (it != last) {
				cout << it->first << " " << it->second << endl;
				++it;
			}
		}
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

Multimap は、正直な印象では map ほど使われていません。やはり [] を使ったアクセスができないことは不便に感じます。

引き続き、ITP2 の問題を紹介していきます。