【C++】STLのset_differenceを使って2つの集合の差分を求める方法

2つの集合の「差（差集合）」とは、1つ目の集合には存在するが、2つ目の集合には存在しない要素だけから構成される集合のことです。set_difference関数によってコピーされる要素は、必ず1つ目の集合から取り出され、元の順序が保たれます。また、この関数を正しく動作させるためには、両方の集合があらかじめソート（整列）されている必要があります。

代表的な集合演算には以下のようなものがあります。

• 和集合（Union）
• 積集合（Intersection）
• 対称差（Symmetric Difference / 排他的論理和）
• 差集合（Difference / 減算）

アルゴリズム

Begin
    集合用のvector v とイテレータ st を宣言する。
    st = set_difference(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 it;
   sort (set1, set1 + 6);
   sort (set2, set2 + 6);
   it = set_difference(set1, set1 + 6, set2, set2 + 6, v.begin());
   v.resize(it - v.begin());
   cout << "The difference between the sets has " << (v.size()) << " elements: "<<endl;
   for (it = v.begin(); it != v.end(); ++it)
      cout<< *it<<" ";
      cout <<endl;
   return 0;
}

コードの解説

まず、2つの整数配列 set1 と set2 を定義し、sort 関数を使ってそれぞれ昇順に並べ替えています。これは、set_difference がソート済みの範囲を前提とするアルゴリズムであるため、非常に重要な手順です。

次に、set_difference の第1引数・第2引数に set1 の先頭と末尾、第3引数・第4引数に set2 の先頭と末尾を渡し、結果の出力先として v.begin() を指定しています。戻り値のイテレータ it は、書き込まれた最後の要素の次の位置を指すため、v.resize(it - v.begin()) によって vector のサイズを実際の要素数に調整しています。

実行結果

The difference between the sets has 4 elements
5 8 9 10

この例では、set1 には存在するが set2 には存在しない要素が「5」「8」「9」「10」の4つであることがわかります。共通する「6」と「7」、および set2 のみに含まれる「1」「2」「3」「4」は結果から除外されています。