Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の9_B問題をC++で解いてみました。
ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#9では、集合演算を学びます。
#9は、alogrithm をインクルードして利用する機能を紹介します。全てのアルゴリズムは、データ構造の実装から切り離されています。アルゴリズムの要件（主にイテレータ）を満たせば動作します。
問題（9_B: Set Intersection）
問題はリンク先をご覧ください。
AOJ ITP2 9_B問題: Set Intersection
積集合を求める set_intersection について学びます。
std::set_intersection について
以下は、cpprefjp 様の記事を参考にさせていただきました。
std::set_intersection は積集合を求めます。
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_intersection(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);2つのソート済み範囲 [first1, last1) と [first2, last2) の積集合を求めます。積集合は、result に格納します。
最大で 2 × ((last1 – first1) + (last2 – first2)) – 1 回の比較を行います。
C++ プログラム例（ITP2 9_B）
2つのソート済の数列AとBが与えられます。AとBの積集合を求めて、要素を出力します。
積集合を set_intersection で求めます（24行目）。set_intersection の最後の引数は、 OutputIterator を指定する必要があります。このためヘルパ関数 inserter を使いました。
以下が、C++プログラムとなります。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int m;
cin >> m;
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
vector<int> result;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(result, result.end()));
sort(result.begin(), result.end());
for (auto it = result.begin(); it != result.end(); ++it) {
cout << *it << endl;
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
前回と同じく，set_intersection については、この問題を解くまで知りませんでした。問題を解くことで新しい機能を学ぶことができました。
引き続き、ITP2 の問題を紹介していきます。
