C++のSTLでset_intersectionを実装し、2つの集合の積集合を求める方法

2つの集合の積集合（インターセクション）とは、両方の集合に共通して含まれる要素だけを集めたものです。set_intersection関数によってコピーされる要素は、必ず最初の集合から取り出され、元の順序がそのまま維持されます。また、この関数を正しく動作させるためには、処理前に両方の集合がそれぞれソート済みである必要があります。

集合に対する代表的な操作には、以下のようなものがあります。

• 和集合（ユニオン）
• 積集合（インターセクション）
• 対称差（排他的論理和・XOR）
• 差集合（減算）

アルゴリズム

Begin
　　結果を格納するvector型変数vとイテレータstを宣言する。
　　st = set_intersection(set1, set1 + n, set2, set2 + n, v.begin()) で初期化する。
　　2つの集合の積集合を出力する。
End.

サンプルコード

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
　　int set1[] = {5,6,7,8,9,10};
　　int set2[] = {1,2,3,4,6,7};
　　vector<int> v(10);
　　vector<int>::iterator st;
　　sort (set1, set1 + 6);
　　sort (set2, set2 + 6);
　　st = set_intersection (set1, set1 + 6, set2, set2 + 6, v.begin());
　　v.resize(st - v.begin());
　　cout << "The intersection between the two set has " << (v.size()) << " elements: "<<endl;
　　for (st = v.begin(); st != v.end(); ++st)
　　　　cout<< *st<<" ";
　　cout <<endl;
　　return 0;
}

コードのポイント

• set_intersectionは第1引数と第2引数に最初の集合の範囲、第3引数と第4引数に2つ目の集合の範囲を指定します。
• 第5引数には結果の出力先（ここではv.begin()）を渡します。
• 戻り値として返されるイテレータは、書き込まれた最後の要素の次の位置を指すため、v.resize(st - v.begin())でベクターのサイズを実際の要素数に調整しています。

実行結果

The intersection between the two set has 2 elements:
6 7

この例では、{5,6,7,8,9,10}と{1,2,3,4,6,7}という2つの配列に共通する要素は6と7の2つであるため、上記のように出力されます。