Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の7_D問題をC++で解いてみました。
ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#7では、集合（set コンテナ）を学びます。
問題（7_D: Multi-Set）
問題はリンク先をご覧ください。
Multiset コンテナについて学びます。
Multiset コンテナについて
以下は、cpprefjp 様の記事を参考にさせていただきました。
概略
Multiset コンテナは、集合を表す連想コンテナを提供します。
- 連想コンテナであり、要素自信がキーとなる。
- 内部の要素は、小さいものから大きなものへとソートされる。
- Set コンテナと異なり要素（キー）の重複を許す。
主なメソッド
よく使われるメソッドを紹介します。
| 名前 | 説明 |
| insert | 要素を挿入する。 |
| erase | 要素を削除する。 |
| size | 要素数を返す。 |
| empty | コンテナが空なら true を、そうでなければ false を返す。 |
| clear | すべての要素を削除する。 |
| find | 指定したキーで要素を探す |
| count | 指定したキーにマッチする要素の数を返す。 |
| lower_bound | 与えられた値より小さくない最初の要素へのイテレータを返す。 |
| upper_bound | 特定の値よりも大きい最初の要素へのイテレータを返す。 |
Multiset コンテナは、二分木を使って実装されるため、insert はコンテナのサイズの対数時間（log）で、erase は定数時間で処理できます。find もコンテナサイズの対数時間（log）で処理できます。ただし、count は、コンテナサイズの対数時間に加えて、その要素の個数にも依存します。
Set コンテナと同じく、二分探索で値を探索できる lower_bound（または upper_bound）も使うことができます。
C++ プログラム例（ITP2 7_D）
問題で与えられるクエリに従い、整数の集合 S に対して、以下の操作を行います。7_C と比較して異なるのは、コンテナの宣言だけです（8行目）。
- クエリ0 insert により、与えられた x をコンテナ S に挿入する。
- クエリ1 コンテナ S に含まれる x の数を出力する。
- クエリ2 コンテナ S から x を削除する。
- クエリ3 コンテナ S から L 以上、R 以下の要素を順番に出力する。
Multiset コンテナで提供されているメソッドを、クエリに従い呼び出します。
#include <iostream>
#include <set>
using namespace std;
int main()
{
multiset<int> S;
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 0) {
int x;
cin >> x;
S.insert(x);
cout << S.size() << endl;
} else if (command == 1) {
int x;
cin >> x;
cout << S.count(x) << endl;
} else if (command == 2) {
int x;
cin >> x;
S.erase(x);
} else if (command == 3) {
int L, R;
cin >> L >> R;
set<int>::iterator it = S.lower_bound(L);
set<int>::iterator last = S.upper_bound(R);
while (it != last) {
cout << *it << endl;
++it;
}
}
}
return 0;
}7_C と比較してプログラムは1行しか異なりませんが、Multiset は重複を許すため、クエリの結果は異なります。
上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
Multiset は、set コンテナほど使われませんが、重複を許したい場合に使われます。トピック#7を通じて、set コンテナについて理解が深まりました。
引き続き、ITP2 の問題を紹介していきます。
