[C#] System.Collections.Generic. SortedDictionary<TKey, TValue> — 赤黒木で実装される整列辞書

System.Collections.Generic.SortedDictionary<TKey, TValue> は、キーで常にソートされた状態を保つ連想配列 です。同じく整列辞書の SortedList<TKey, TValue> が配列ベースで実装されているのに対し、SortedDictionary は 赤黒木（self-balancing binary search tree） で実装されており、挿入・削除に強いのが特徴です。

`SortedDictionary<TKey, TValue>` とは

名前空間：System.Collections.Generic
内部構造：赤黒木（バランス二分探索木）
キーの並びは IComparable<TKey> または IComparer<TKey> に従う昇順
キー重複・null 不可（ただし null 比較を許す IComparer<TKey> を渡せば null キーも可）

var prices = new SortedDictionary<string, int>
{
    ["banana"] = 100,
    ["apple"]  = 150,
    ["cherry"] = 300,
};

foreach (var (k, v) in prices)
    Console.WriteLine($"{k} = {v}");
// apple, banana, cherry の順

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

インターフェース	役割
`IDictionary<TKey, TValue>`	ジェネリックな連想コレクション
`IReadOnlyDictionary<TKey, TValue>`	読み取り専用ビュー
`ICollection<KeyValuePair<TKey, TValue>>`	要素単位での操作
`IReadOnlyCollection<KeyValuePair<TKey, TValue>>`	読み取り専用 `Count`
`IEnumerable<KeyValuePair<TKey, TValue>>`	キー昇順で列挙
`IDictionary` / `ICollection` / `IEnumerable`	非ジェネリック互換

IDictionary<TKey, TValue> の構成は Dictionary<TKey, TValue> の記事を、非ジェネリック IDictionary は Hashtable の記事を参照してください。

IEnumerable<T> は IEnumerable と IEnumerator の記事を参照。

キーの順序 — `IComparer<TKey>`

並びは既定で Comparer<TKey>.Default（TKey が IComparable<TKey> を実装していること）。独自比較は IComparer<TKey> で。

var byLen = new SortedDictionary<string, int>(
    Comparer<string>.Create((a, b) =>
    {
        int diff = a.Length - b.Length;
        return diff != 0 ? diff : string.CompareOrdinal(a, b);
    }));

byLen["banana"] = 1;
byLen["apple"]  = 2;
byLen["kiwi"]   = 3;
// kiwi → apple → banana の順

主な API と計算量

操作	API	計算量
取得	`[key]` / `TryGetValue`	O(log n)
追加	`Add(k, v)` / `[k] = v`	O(log n)
削除	`Remove(k)`	O(log n)
含有判定	`ContainsKey(k)`	O(log n)
値検索	`ContainsValue(v)`	O(n)
列挙	`foreach`	O(n)（キー昇順）

すべての主要操作が O(log n) で安定。挿入・削除が頻繁でも性能が劣化しません。これが SortedList との最大の違いです。

`Dictionary<TK,TV>` / `SortedList<TK,TV>` / `SortedDictionary<TK,TV>` の比較

観点	`Dictionary<TK,TV>`	`SortedList<TK,TV>`	`SortedDictionary<TK,TV>`
内部構造	ハッシュテーブル	ソート済み配列	赤黒木
取得（キー）	O(1)	O(log n)	O(log n)
挿入・削除	O(1)	O(n)	O(log n)
順序保持	✕	◯ キー昇順	◯ キー昇順
インデックス取得	×	◯ `Keys[i]` / `Values[i]`	×
メモリ効率	中	◯ コンパクト	× ノードのオーバーヘッド大

選び分けの指針：

順序不要・最速 → Dictionary<TK,TV>
作成後ほぼ読み取りのみ・順序保持・メモリ重視・インデックス参照あり → SortedList<TK,TV>
頻繁な挿入・削除＋順序保持 → SortedDictionary<TK,TV>

範囲列挙との関係

赤黒木ベースなので、本来は 「あるキー以上の要素を順に列挙」 が高速にできるはずですが、SortedDictionary<TK,TV> 自体には範囲列挙の API がありません。ソート済みのキーで範囲を扱いたい場合は次を検討します。

SortedSet<T> の GetViewBetween(lower, upper)（後の記事で解説）
ImmutableSortedDictionary<TK,TV>（イミュータブル版、追加 API あり）

SortedDictionary<TK,TV>.Keys を LINQ の Where で絞ってもいいですが、線形走査になる点に注意。

メモリ・キャッシュ局所性

SortedDictionary<TK,TV> は 木のノードを個別に確保 するためメモリオーバーヘッドが大きく、キャッシュ局所性も SortedList より劣ります。要素数が固定的で読み取り中心なら SortedList のほうが速いことも多いです。

使いどころ

1. 頻繁に挿入・削除しつつキー順を維持したい

優先度付きスケジューリング、時系列のイベントマップ、リアルタイムに更新されるランキングなど。書き換え主体で順序が必要 な場面で本領発揮。

2. 範囲指定の処理

「ある日付以降の予定をすべて列挙」など、キーが連続的に意味を持つ場面。範囲取得 API は無いものの、Keys を昇順で走査して途中で抜ける書き方は素直に O(log n + k) で動きます（前半の O(log n) は到達点を見つける部分の代替手段次第）。

3. テスト容易性

挿入順に依存しない決定的な列挙順が欲しいとき。Dictionary の列挙順は仕様としては未定義ですが、SortedDictionary はキー順で常に同じ結果になるため、ゴールデンテストで安定して扱えます。

向かないケース

順序が要らない → Dictionary<TK,TV> のほうが O(1) で速い
読み取り中心・メモリ重視 → SortedList<TK,TV>
位置（インデックス）でアクセスしたい → SortedList<TK,TV> のみ対応
並行アクセス → 標準では並行版が無い。読み書きすべてロックで保護するか、ImmutableSortedDictionary<TK,TV> を検討

注意点

null キーは不可（既定の比較子の場合）。値型 TKey でも Nullable<T> にしない限り null は入らない。
列挙中の変更は例外。
スレッドセーフではない。

まとめ

SortedDictionary<TKey, TValue> は 赤黒木で実装された整列辞書。
IDictionary<TK,TV> / IReadOnlyDictionary<TK,TV> 等を実装し、列挙はキー昇順。
取得・挿入・削除すべてが O(log n)。書き換え主体＋順序保持 に最適。
順序不要なら Dictionary<TK,TV>、読み取り中心で省メモリなら SortedList<TK,TV> を選ぶ。

SortedDictionary<TKey, TValue> とは