第19回 std::set / std::unordered_set ― 重複を許さない集合

std::set は重複のない値の集合で、要素は自動でソートされます。「すでに見た ID か？」「ユニークな要素を列挙」などの存在確認が主な用途。さらに、順序は要らず速さだけ欲しいなら、ハッシュ版の std::unordered_set が平均 O(1) で動きます。本章では 2 つの set の使い分けと、集合演算（set_intersection など）の基本を整理します。

このページで押さえること

✅ 最低限ここだけ覚える

s.insert(x)：重複は自動で無視される
存在確認は s.count(x) > 0 または s.contains(x)（C++20）
std::set：ソート済み・O(log n)
std::unordered_set：順序なし・O(1) 平均

⭐ 余裕があれば読む

tree 版と hash 版の使い分け基準
集合演算（set_intersection など）
std::multiset（重複を許す版）
vector に詰めて sort + unique のほうが速い場面

1. まず触ってみる ― set に値を追加する

下のフィールドに数を入れて insert を何度か押してみてください。同じ値を複数回入れても重複しないこと、並びが自動でソートされることが見えます。

▶ std::set<int> のインタラクティブ操作

値:

よくある素朴な疑問

Q. set は map と何が違う？
→ map はキーと値のペア、set は値だけ。構造的には map の「キーだけ版」と考えて OK。用途も「重複なしの値の集まり」「ある値が存在するか調べる」といった集合的なものに特化。

Q. set なのにソートされるのはなぜ？
→ std::set は内部が平衡二分木（赤黒木）で実装されているため、並びが自然とソート順になります。これが tree 版の set の特徴。順序が不要ならハッシュ版（unordered）のほうが速い。

Q. 重複を許して個数を数えたい場合は？
→ std::multiset（同じ値を何個でも保持）か、std::map<T, int>（値 → 個数）のカウンタ方式が一般的。

2. std::set の基本操作

重複を許さない値の集合。要素の存在確認が主な用途です。

set 基本C++

#include <set> std::set<int> s; s.insert(5); // 追加 s.insert(3); s.insert(5); // 重複なので無視される s.insert(1); // s は {1, 3, 5} (ソート済み) if (s.count(3) > 0) { // 存在確認 // ある } s.erase(3); // 削除 // s は {1, 5} for (int x : s) std::cout << x << ' '; // 1 5 （昇順）

よく使うメソッド

s.insert(x) ― 追加（既存なら何もしない）
s.erase(x) ― 削除
s.count(x) ― 0 or 1。存在確認の定番
s.contains(x) ― C++20 から。意味がより明快
s.size() / s.empty() ― 他コンテナと共通
s.find(x) ― 見つかれば反復子、なければ s.end()

自作クラスを set に入れるには： 内部が二分木なので、要素同士の 大小比較 が要ります。operator< を定義するか、比較関数を std::set<T, Compare> の第 2 引数で渡します。第 28 回自作クラスを std::sort で並べるで扱った operator< がそのまま使えます。

3. std::unordered_set ― ハッシュ版

同じ「重複なしの集合」でも、内部がハッシュテーブルの版があります。順序を捨てる代わりに検索／挿入／削除が平均 O(1)。

std::settree / O(log n)

#include <set> std::set<int> s = {5, 1, 3}; for (int x : s) std::cout << x; // 出力: 1 3 5 ← 昇順で列挙

std::unordered_sethash / O(1) 平均

#include <unordered_set> std::unordered_set<int> us = {5, 1, 3}; for (int x : us) std::cout << x; // 出力: 順序不定（例: 5 3 1）

使い分けの判断

観点	`std::set`（tree）	`std::unordered_set`（hash）
計算量	O(log n)	O(1) 平均（最悪 O(n)）
順序	昇順で列挙できる	順序なし
「最小値」取り出し	`*s.begin()` で可能	全走査が必要
自作キー型	`operator<` が必要	`std::hash` の特殊化が必要
選ぶ基準	順序が要る／範囲クエリ	速さ最優先／順序不要

ハッシュ衝突に注意： unordered_* は平均 O(1) ですが、ハッシュが偏ると最悪 O(n) まで落ちます。キー分布が怪しい場面（ユーザー入力など）では set のほうが安定。ライブラリ標準の std::hash<int> や std::hash<std::string> は通常問題になりません。

4. 集合演算（`set_intersection` など）

set の特徴を活かした集合演算も標準ライブラリ（<algorithm>）にあります。

積集合を求めるalgorithm

#include <algorithm> #include <iterator> std::set<int> a = {1, 2, 3, 4}; std::set<int> b = {3, 4, 5, 6}; std::vector<int> common; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(common)); // common = {3, 4}

他にも：

std::set_union ― 和集合
std::set_difference ― 差集合
std::set_symmetric_difference ― 対称差

これらは「ソート済みの 2 つの区間」を前提としており、std::set に加え、std::sort 済みの std::vector にも適用できます。詳しくは STEP 9 の「集合演算アルゴリズム」で扱います。

5. 使い所と vector との使い分け

set が効くケース：

「すでに見た ID」を記録して重複排除 → unordered_set
「ユニークな単語を辞書順で列挙」→ set
2 つの集合の積・和・差を計算したい → set + set_intersection など

実は vector でも足りることが多い： 最終的にソート済みの一覧が欲しいだけなら、vector に詰めて std::sort + std::unique + erase のほうがキャッシュ効率が良く、実測で set より速いことがよくあります。

判断基準：「途中で存在確認や挿入／削除を繰り返す」なら set、「最後にまとめてユニーク化」なら vector + sort + unique。

確認クイズ

3 問。

Q1. `std::set<int> s; s.insert(3); s.insert(3); s.insert(3);` の後、`s.size()` は？

コンパイルエラー

set は重複を許さない。同じ値を何度 insert しても、すでにあれば挿入されません。だから size は 1。複数個保持したければ std::multiset を使うか、std::vector に詰めます。

Q2. `std::unordered_set<std::string>` を選ぶ適切なケースは？

単語を辞書順に並べたい

要素を追加した順に取り出したい

大量の単語から重複を排除して、その単語が出たかを素早くチェック

同じ単語を複数回カウントしたい

unordered_set は O(1) 平均で「存在チェック」ができる、順序は不要な集合。①は set（sorted）、②は vector、④は unordered_map で count。

Q3. 自作クラス `Student` を `std::set<Student>` に入れるために必要なのは？

Student に operator== を定義する

Student に operator< を定義する（または比較関数を第 2 引数で渡す）

Student に hash 関数を定義する

何もしなくても使える

std::set は内部が二分木で、要素の大小比較で並べて保持します。operator< が必要。operator== は不要（!(a<b) && !(b<a) で等価を判定）。hash は unordered_set を使う場合に必要。