【C++】std::set_union 等 | 2つのソート済みコンテナで集合演算を行う方法

2025年8月31日

はじめに

数学で学ぶ「集合」の考え方（和集合、積集合、差集合など）は、プログラミングにおいても、2つのデータセットを比較・合成する際に非常に役立ちます。

C++の標準ライブラリ <algorithm> は、これらの集合演算を効率的に行うための、以下の4つの主要な関数を提供しています。

set_union: 和集合（どちらかに含まれる全ての要素）
set_intersection: 積集合（両方に共通して含まれる要素）
set_difference: 差集合（最初の集合にのみ含まれる要素）
set_symmetric_difference: 対称差集合（どちらか一方にのみ含まれる要素）

この記事では、これらの関数を使って、2つのソート済み vector から、様々な集合を生成する方法を解説します。

【重要】事前条件: 範囲はソート済みであること

これらの集合演算アルゴリズムが正しく動作するためには、大前提として、入力となる2つのコンテナ（範囲）の要素が、あらかじめ同じ基準でソート（昇順に整列）されている必要があります。ソートされていない範囲に対して使用すると、結果は保証されません。

集合演算のサンプルコード

このコードは、ソート済みの2つの vector groupA と groupB を用意し、それらに対して4種類全ての集合演算を実行し、結果を出力します。

完成コード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // 集合演算アルゴリズム
#include <iterator>  // back_inserter

using namespace std;

// 結果を分かりやすく表示するためのヘルパー関数
void print_vector(const string& title, const vector<int>& vec) {
    cout << title << ": { ";
    for (int val : vec) {
        cout << val << " ";
    }
    cout << "}" << endl;
}

int main() {
    // 事前にソート済みの2つのvectorを準備
    vector<int> groupA = {10, 20, 30, 40, 50};
    vector<int> groupB = {30, 40, 60, 70};

    print_vector("グループA", groupA);
    print_vector("グループB", groupB);
    cout << "--------------------" << endl;

    // --- 1. 和集合 (Union) ---
    vector<int> union_result;
    set_union(groupA.begin(), groupA.end(),
              groupB.begin(), groupB.end(),
              back_inserter(union_result));
    print_vector("和集合 (A ∪ B)", union_result);

    // --- 2. 積集合 (Intersection) ---
    vector<int> intersection_result;
    set_intersection(groupA.begin(), groupA.end(),
                     groupB.begin(), groupB.end(),
                     back_inserter(intersection_result));
    print_vector("積集合 (A ∩ B)", intersection_result);
    
    // --- 3. 差集合 (Difference) ---
    vector<int> difference_result;
    set_difference(groupA.begin(), groupA.end(),
                   groupB.begin(), groupB.end(),
                   back_inserter(difference_result));
    print_vector("差集合 (A - B)", difference_result);

    // --- 4. 対称差集合 (Symmetric Difference) ---
    vector<int> sym_difference_result;
    set_symmetric_difference(groupA.begin(), groupA.end(),
                             groupB.begin(), groupB.end(),
                             back_inserter(sym_difference_result));
    print_vector("対称差集合", sym_difference_result);

    return 0;
}