第58回集合演算アルゴリズム

ソート済みの 2 つの範囲に対する和集合・積集合・差集合・対称差を O(m+n) で求めるアルゴリズム。集合論の操作を STL で 1 行で書けます。

1. 一覧

関数	意味	例: A={1,2,3}, B={2,3,4}
`std::set_union`	A ∪ B（どちらかに含まれる）	{1,2,3,4}
`std::set_intersection`	A ∩ B（両方に含まれる）	{2,3}
`std::set_difference`	A - B（A にあり B にない）	{1}
`std::set_symmetric_difference`	(A-B) ∪ (B-A)	{1,4}
`std::includes`	B ⊆ A か	false
`std::merge`	2 つのソート済み列をマージ	{1,2,2,3,3,4}

共通の前提：入力範囲はソート済みでなければいけません（ソートされていないと結果が正しくない）。

2. 典型例

set 演算 4 つC++

#include <algorithm> std::vector<int> a = {1,2,3,4}; std::vector<int> b = {3,4,5,6}; std::vector<int> out; // 和集合 {1,2,3,4,5,6} std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // 積集合 {3,4} out.clear(); std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // 差集合 A-B {1,2} out.clear(); std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));

A = {1,2,3,4}, B = {3,4,5,6}

A ∪ B = {1,2,3,4,5,6}

A ∩ B = {3,4}

A - B = {1,2}

対称差 = {1,2,5,6}

3. vector vs std::set のどちらを使う？

ソート済み vector軽量

std::vector<int> a = {1,2,3,4}; std::vector<int> b = {3,4,5}; // 必要ならソートしておく // set_* を適用 // キャッシュ効率良、メモリ少

std::set常時ソート

std::set<int> a = {1,2,3,4}; std::set<int> b = {3,4,5}; // 挿入時点で自動ソート // set_* をそのまま適用 // ノード型でキャッシュ効率低

目安：集合演算を 1 回だけ → vector+sort が速い。頻繁に更新しながら使う → std::set。

確認クイズ

Q1. `std::set_union` が要求する入力は？

任意の順序

ソート済みの 2 つの範囲

std::set のみ

重複なし

set_* 系はすべてソート済み前提。ソートされていないと結果が不正。

Q2. A={1,2,3}, B={2,3,4} の対称差 (set_symmetric_difference) は？

{1,2,3,4}

{2,3}

{1,4}

{1,2,3}

対称差 = どちらか片方だけに含まれる要素。A-B={1} と B-A={4} の和集合。

Q3. 結果を出力する一般的な書き方は？

出力 vector を先に確保

std::back_inserter で push_back しながら出力

printf で直接出力

結果サイズを事前計算

back_inserter なら出力サイズが未知でも柔軟。サイズが分かっていれば out.resize(...) して out.begin() でも可。

Q4. 「1 回だけ集合演算する」ケースで速いのは？

std::set に入れて set_*

vector + sort + set_*

手書きの for ループ

map に入れる

vector はメモリ連続でキャッシュ効率が良いので、一発 sort + set_* が最速パターンが多い。std::set はノード型でメモリが散在。