【C++】STLのset_symmetric_differenceで集合の対称差を実装するプログラム

本記事では、C++の標準テンプレートライブラリ（STL）に含まれる set_symmetric_difference 関数を使って、2つの集合の「対称差」を求めるプログラムを紹介します。

対称差とは、2つの集合のうち「どちらか一方にだけ存在し、両方には存在しない」要素から構成される集合のことです。

主な集合演算の種類

• 和集合（Union）：どちらか一方に含まれるすべての要素
• 積集合（Intersection）：両方に共通して含まれる要素
• 対称差（Symmetric Difference ／ 排他的論理和 XOR）：片方にのみ含まれる要素
• 差集合（Difference ／ 減算）：一方から他方の要素を取り除いた残り

アルゴリズム

Begin
    集合格納用のベクトルvとイテレータstを宣言する。
    st = set_symmetric_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 st;
    sort (set1, set1 + 6);
    sort (set2, set2 + 6);
    st = set_symmetric_difference(set1, set1 + 6, set2, set2 + 6, v.begin());
    v.resize(st - v.begin());
    cout<<"2つの集合の対称差は "<< (v.size())<< " 個の要素で構成されます: "<<endl;
    for (st = v.begin(); st != v.end(); ++st)
        cout<< *st<<" ";
    cout <<endl;
    return 0;
}

実行結果

2つの集合の対称差は 8 個の要素で構成されます:
1 2 3 4 5 8 9 10

コードの解説

set_symmetric_difference を使用する前に、入力となる2つの配列が必ずソート済みである必要があります。そのため、sort() でそれぞれの配列を昇順に並べ替えています。

set_symmetric_difference(first1, last1, first2, last2, result) は、第1引数～第2引数で指定した範囲と、第3引数～第4引数で指定した範囲の対称差を計算し、その結果を第5引数で指定した出力先（ここではベクトル v の先頭）へ書き込みます。戻り値は出力先の末尾を指すイテレータであり、これを利用して v.resize(st - v.begin()) とすることで、実際に格納された要素数ぴったりにベクトルのサイズを調整しています。

この例では、両方の配列に共通して含まれる 6 と 7 が除外され、残りの 8 個の要素（1, 2, 3, 4, 5, 8, 9, 10）が出力されます。