[C#] System.Collections.SortedList — キーで自動整列される連想配列の仕組みと使いどころ

System.Collections.SortedList は、キーで常にソートされた状態を保つ連想配列 です。Hashtable がハッシュベースなのに対し、SortedList は 二つの配列（キー用と値用）+ 二分探索 で実装されているのが特徴です。「順序が必要な辞書」「インデックスでもアクセスしたい辞書」といった要件を一つのクラスで満たします。

`SortedList` とは

名前空間：System.Collections
内部構造：object[] keys（ソート済み）+ object[] values
キーの並びは IComparable か、コンストラクタに渡した IComparer に従う
キーは重複不可、null 不可。値は null 可

using System.Collections;

var list = new SortedList
{
    { "banana", 100 },
    { "apple",  150 },
    { "cherry", 300 },
};

// キーで整列されているので apple → banana → cherry の順
foreach (DictionaryEntry e in list)
    Console.WriteLine($"{e.Key} = {e.Value}");

// インデックスアクセスもできる
object? firstKey   = list.GetKey(0);    // "apple"
object? firstValue = list.GetByIndex(0);// 150

Hashtable と違い、GetKey(int) / GetByIndex(int) のように 位置（インデックス）でも要素にアクセスできる のが SortedList 独特の特徴です。

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

インターフェース	役割
`IDictionary`	キー・値の組を扱う連想コレクション
`ICollection`	`Count` / `CopyTo` / 同期サポート
`IEnumerable`	`foreach` で `DictionaryEntry` を列挙（キー昇順）
`ICloneable`	`Clone()` で浅いコピー

各インターフェースの詳細は次を参照してください。

IDictionary: Hashtable の記事
ICollection: ArrayList の記事
IEnumerable: IEnumerable と IEnumerator の記事
ICloneable: ICloneable インターフェースの記事

キーの順序 — `IComparable` と `IComparer`

キーは既定で IComparable.CompareTo を使って整列されます。独自の比較ロジックを使いたいときはコンストラクタに IComparer を渡します。

public class LengthComparer : IComparer
{
    public int Compare(object? x, object? y)
    {
        var sx = (string)x!;
        var sy = (string)y!;
        int diff = sx.Length - sy.Length;
        return diff != 0 ? diff : string.CompareOrdinal(sx, sy);
    }
}

var byLen = new SortedList(new LengthComparer())
{
    { "banana", 1 }, { "apple", 2 }, { "kiwi", 3 },
};
// kiwi → apple → banana

文字列なら StringComparer.OrdinalIgnoreCase のような既製の比較子も使えます。

主な API と計算量

操作	API	計算量
取得（キー）	`[key]`	O(log n)（二分探索）
取得（インデックス）	`GetByIndex(i)` / `GetKey(i)`	O(1)
追加	`Add(key, value)` / `[key] = v`	O(n)（配列に挿入してずらす）
削除	`Remove(key)` / `RemoveAt(i)`	O(n)
キー検索	`ContainsKey(key)` / `IndexOfKey(key)`	O(log n)
値検索	`ContainsValue` / `IndexOfValue`	O(n)
列挙	`foreach`	O(n)

読み取りは速く（O(log n) または O(1)）、書き込みは遅い（O(n)） のが SortedList の性能特性です。挿入・削除のたびに配列内の要素をずらすコストがかかるためです。

`SortedList` vs `SortedDictionary<TKey, TValue>` vs `Dictionary<TKey, TValue>`

「キーでソートされた辞書」が欲しいときの選択肢は次の 3 つです。

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

選び方の指針：

一度作って ほとんど読み取りしかしない → SortedList<TK,TV>（メモリ効率良）
頻繁に挿入・削除 が走る → SortedDictionary<TK,TV>
順序が要らないなら最速の Dictionary<TK,TV>

`SortedList<TKey, TValue>` との比較

非ジェネリックな SortedList は値型でボックス化が発生するため、現在の標準は System.Collections.Generic.SortedList<TKey, TValue> です。API はほぼ同じで、型安全 + ボックス化なし。新規コードでは常にジェネリック版 を選びましょう。

// Generic 版
var prices = new System.Collections.Generic.SortedList<string, int>
{
    { "apple", 150 }, { "banana", 100 },
};

foreach (var (k, v) in prices)
    Console.WriteLine($"{k} = {v}");

string firstKey = prices.Keys[0];   // インデックスでアクセス（IList<TKey>）
int    firstVal = prices.Values[0];

使いどころ

1. 整列順で列挙したい辞書

設定値、ID → 名前のマップなど、キー昇順で表示・出力したい 場合に向きます。

var settings = new System.Collections.Generic.SortedList<string, string>(LoadConfig());
foreach (var (key, value) in settings)
    Console.WriteLine($"{key} = {value}"); // 自動でキー昇順

2. 範囲取得・近傍検索

IndexOfKey で位置を二分探索し、GetKey(i) / GetByIndex(i) で前後の要素にアクセスできます。

var ts = new System.Collections.Generic.SortedList<DateTime, double>(measurements);

// 指定時刻以降の最初のエントリを探す
int idx = 0;
for (int i = 0; i < ts.Count; i++)
    if (ts.Keys[i] >= target) { idx = i; break; }

SortedDictionary ではこの種のインデックスアクセスができないため、位置参照が必要なら SortedList 一択 です。

3. メモリを節約したい読み取り中心の辞書

データを起動時に読み込み、ほぼ読み取りだけで運用するシナリオ（マスターデータ、辞書、ローカライズリソースなど）に向きます。配列ベースなのでキャッシュ効率もよく、SortedDictionary より省メモリです。

向かないケース

大量データへの 頻繁な挿入・削除 → 都度 O(n) コピーが走る。SortedDictionary のほうが良い。
順序が不要 → ハッシュベースの Dictionary のほうが速い。

まとめ

SortedList は キーでソートされた連想配列。内部はソート済みキー配列＋値配列。
IDictionary / ICollection / IEnumerable / ICloneable を実装。
キー検索は O(log n)、インデックス検索は O(1)、挿入・削除は O(n)。
順序保持＋インデックスアクセスが両方欲しいときに最適。新規コードでは ジェネリック版 SortedList<TKey, TValue> を使う。
頻繁な書き換えがあるなら SortedDictionary<TKey, TValue>、順序不要なら Dictionary<TKey, TValue>。

SortedList とは