[C#] System.Collections.Generic.SortedSet<T> — 赤黒木で実装される整列セット

System.Collections.Generic.SortedSet<T> は、重複のない要素を整列状態で保持するコレクション です。HashSet<T> がハッシュベースなのに対し、SortedSet<T> は 赤黒木（バランス二分探索木）で実装されており、要素を昇順で列挙でき、範囲ビューも取れるのが特徴です。.NET 4.0 で追加されました。

`SortedSet<T>` とは

名前空間：System.Collections.Generic
内部構造：赤黒木
重複不可、null 不可（既定比較子の場合）
並びは IComparer<T> に従う昇順
集合演算（和・積・差・対称差）の API を持つ

var set = new SortedSet<int> { 5, 1, 3, 5, 2 }; // 重複の 5 は一度しか入らない
foreach (var x in set) Console.Write($"{x} ");  // 1 2 3 5

set.Add(4);
set.Remove(3);

int min = set.Min;   // 1
int max = set.Max;   // 5

サポートするインターフェース

インターフェース	役割
`ISet<T>`	集合演算をもつコレクション
`IReadOnlySet<T>`	読み取り専用の集合（.NET 5+）
`ICollection<T>`	`Count` / `Add` / `Remove` 等
`IReadOnlyCollection<T>`	読み取り専用 `Count`
`IEnumerable<T>`	昇順で列挙
`ICollection` / `IEnumerable`	非ジェネリック互換

ISet<T> は集合特有の API を規定するインターフェースです。

public interface ISet<T> : ICollection<T>
{
    new bool Add(T item);                       // 追加できたら true
    void UnionWith(IEnumerable<T> other);       // 和集合（破壊的）
    void IntersectWith(IEnumerable<T> other);   // 積集合
    void ExceptWith(IEnumerable<T> other);      // 差集合
    void SymmetricExceptWith(IEnumerable<T> other); // 対称差
    bool IsSubsetOf(IEnumerable<T> other);
    bool IsSupersetOf(IEnumerable<T> other);
    bool IsProperSubsetOf(IEnumerable<T> other);
    bool IsProperSupersetOf(IEnumerable<T> other);
    bool Overlaps(IEnumerable<T> other);
    bool SetEquals(IEnumerable<T> other);
}

ICollection の詳細は ArrayList の記事、IEnumerable / IEnumerator は IEnumerable と IEnumerator の記事を参照してください。

主な API と計算量

操作	API	計算量
追加	`Add(item)`	O(log n)
削除	`Remove(item)`	O(log n)
含有判定	`Contains(item)`	O(log n)
最小・最大	`Min` / `Max`	O(log n)
範囲ビュー	`GetViewBetween(lo, hi)`	O(log n) で取得、列挙は O(k)
集合演算	`UnionWith` 等	O((n + m) log n)
列挙	`foreach`	O(n)（昇順）

すべての主要操作が O(log n) で安定。HashSet<T> の O(1) には敵いませんが、順序が必要な場面ではこちらを選びます。

範囲ビュー — `GetViewBetween`

SortedSet<T> の真骨頂が GetViewBetween(lower, upper)。指定範囲の 生きたビュー（元のセットを参照する SortedSet）を返します。

var set = new SortedSet<int> { 1, 3, 5, 7, 9, 11 };
SortedSet<int> view = set.GetViewBetween(3, 9);

foreach (var x in view) Console.Write($"{x} "); // 3 5 7 9

view.Add(6);   // 元のセットにも反映される
view.Remove(5);

ビューは 書き戻しも可能 で、範囲外を追加しようとすると例外。SortedDictionary<TK,TV> には無いこの範囲列挙は、時系列処理やレンジクエリで強力な武器になります。

集合演算

UnionWith / IntersectWith / ExceptWith / SymmetricExceptWith で和・積・差・対称差を 破壊的 に計算します。

var a = new SortedSet<int> { 1, 2, 3, 4 };
var b = new SortedSet<int> { 3, 4, 5, 6 };

var c = new SortedSet<int>(a);
c.UnionWith(b);                        // {1, 2, 3, 4, 5, 6}

var d = new SortedSet<int>(a);
d.IntersectWith(b);                    // {3, 4}

「もとを壊さずに集合演算したい」なら、必ずコピーを作ってから呼びます。

`HashSet<T>` との比較

観点	`HashSet<T>`	`SortedSet<T>`
内部構造	ハッシュテーブル	赤黒木
追加・削除・含有	O(1)	O(log n)
列挙順	未定義	昇順
範囲ビュー	×	◯ `GetViewBetween`
メモリ効率	◯	× ノードのオーバーヘッド
推奨	順序不要なら最速	順序・範囲が必要なら

HashSet<T> も ISet<T> を実装しており、API レベルではほぼ互換。順序や範囲列挙が要らないなら HashSet<T> のほうが断然速い ので、要件に応じて使い分けます。

カスタム比較子

要素のソート順をカスタマイズしたいときは IComparer<T> をコンストラクタで渡します。

var byAbs = new SortedSet<int>(
    Comparer<int>.Create((a, b) => Math.Abs(a).CompareTo(Math.Abs(b))));

byAbs.Add(-3);
byAbs.Add(1);
byAbs.Add(-2);
foreach (var x in byAbs) Console.Write($"{x} "); // 1 -2 -3

注意：「等価」と判定された要素は重複扱い で追加されません。abs(-3) == abs(3) なら片方しか入らない、ということ。

使いどころ

1. 順序付きユニーク集合

イベント時刻・スコアなど、昇順で参照したいユニーク値の集合。HashSet<T> で集めて OrderBy でソートする方法と比べ、追加時点で常に整列している点が利点。

2. 範囲クエリ

「日付 X から Y までのイベントを列挙」「スコア上位 K 件」などのレンジ系クエリ。GetViewBetween がそのまま使えます。

var schedule = new SortedSet<DateTime>(allTimes);
var thisWeek = schedule.GetViewBetween(DateTime.Today, DateTime.Today.AddDays(7));
foreach (var t in thisWeek) Console.WriteLine(t);

3. ストリーム処理での自動整列

データをストリームで受け取りつつ常に整列状態を維持したいとき。挿入が O(log n) なので、毎回ソートし直すよりずっと効率的。

4. スカイライン問題などのアルゴリズム

「現在生きているイベントの中で最大値を取る」といった処理は、Max プロパティが O(log n) で取れる SortedSet<T> がぴったりはまります。

向かないケース

順序不要・最速 → HashSet<T>
キーと値のペアが必要 → SortedDictionary<TK,TV>
並行アクセス → 標準では並行版なし。ImmutableSortedSet<T> を検討

注意点

null 不可（既定比較子の場合）。
列挙中の変更は例外。
スレッドセーフではない。
GetViewBetween のビューは生きたビュー。元のセットの変更が伝播する。

まとめ

SortedSet<T> は 赤黒木で実装された整列ユニーク集合。
ISet<T> / IReadOnlySet<T> / ICollection<T> 等を実装し、列挙は昇順。
追加・削除・含有・Min/Max がすべて O(log n)。
GetViewBetween で 範囲ビュー が取れるのが最大の特徴。
順序不要なら [HashSet]、キー・値ペアなら SortedDictionary<TK,TV> を選ぶ。

SortedSet<T> とは