C++のSTLでset_unionを使って2つの集合の和集合を求める方法

2つの集合の和集合(union)とは、どちらか一方の集合、あるいは両方の集合に存在する要素によって構成される集合のことです。第1の集合に同じ値がすでに存在する場合、第2の集合側のその要素は結果の集合にはコピーされません。

主な集合演算

集合に対する基本的な演算には、以下の4種類があります。

• 和集合(Union)
• 積集合(Intersection)
• 対称差(Symmetric Difference / 排他的論理和)
• 差集合(Difference)

set_unionを使う際のポイント

STLのstd::set_unionを使用する前に、必ず両方の入力範囲をソートしておく必要があります。このアルゴリズムはソート済みの範囲を前提として動作するため、未ソートのデータを渡すと正しい結果が得られません。また、戻り値として「結果の末尾を指すイテレータ」が返されるため、これを使って実際に書き込まれた要素数だけコンテナのサイズを調整します。

アルゴリズム

Begin
    配列 set1、set2、vector型の v、イテレータ st を宣言する。
    st ← set_union(set1, set1+n, set2, set2+n, v.begin())
    結果として得られた要素を出力する。
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;

    // set_union を使う前に、両方の配列をソートしておく
    sort (set1, set1 + 6);
    sort (set2, set2 + 6);

    // 和集合を計算し、戻り値(結果の末尾イテレータ)を受け取る
    st = set_union(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つの集合の和集合は 10 個の要素を持ちます:
1 2 3 4 5 6 7 8 9 10