C# 中的 SortedList 怎么用？底层原理、常用操作与常见问题一次讲透

SortedList 是 .NET 基础类库中一个比较特别的键值对集合，它虽然名字里带有 List，却和普通列表的定位完全不同，主要用途是保存一组按键排序的键值数据。它位于 System.Collections.Generic 命名空间，泛型版本写作 SortedList<TKey,TValue>；在非泛型时代还有 System.Collections.SortedList，但由于泛型版本类型安全且性能更好，现在多数场景应该优先使用泛型版本。

从内部实现来看，SortedList 并没有使用链表或树结构，而是用两个长度始终一致的数组分别存储键和值。每次插入或删除元素时，它通过二分查找在键数组中定位目标位置，然后利用数组复制操作搬移后续元素。这种结构决定了它的读取性能很好，而写入性能相对较重。

一、底层结构：双数组加二分查找

SortedList<TKey,TValue> 最核心的设计是双数组。它内部维护一个键数组和一个值数组，两者的长度和版本同步变化。插入数据时，类会先根据键比较器在键数组上执行二分查找，找到应该插入的位置；如果这个位置已经存在相同的键，直接抛出 ArgumentException。如果没有重复，则通过 Array.Copy 把插入位置及其后面的元素整体向后移动一位，腾出空位后写入新键和新值。正因为需要搬移数组，插入操作的时间复杂度是 O(n)。

读取操作则不同。由于键数组始终按比较器规则有序，查询特定键时可以直接用二分查找，时间复杂度稳定为 O(log n)。删除操作同样先查找键位置，然后把后续元素前移，复杂度也是 O(n)。因此 SortedList 的典型适用场景是读多写少、需要按键顺序遍历的集合。

SortedList 还有一个容量概念由 Capacity 属性表示。内部数组在元素增加时会自动扩容，一般会一次分配更大的连续空间以降低频繁复制带来的开销。如果提前知道数据规模，可以通过构造函数指定初始容量，减少运行期的数组重新分配次数。

二、核心操作：增删改查怎么用

创建 SortedList 后，最常见的写入方式是 Add 方法和索引器。Add 方法接收键和值，如果键已存在会抛异常；索引器在访问不存在的键时，如果作为读取使用会抛出 KeyNotFoundException，但如果作为赋值目标使用，则会自动添加新项。这一点容易让人混淆，实际项目中更推荐用 TryGetValue 来读取，避免异常参与正常控制流程。

下面代码演示了初始化、添加、读取、判断存在、覆盖和遍历的基本操作。

using System;
using System.Collections.Generic;

var scores = new SortedList<string, int>();

// 添加数据
scores.Add("Alice", 90);
scores.Add("Bob", 85);
scores["Cindy"] = 95;

// 读取：最好使用 TryGetValue
if (scores.TryGetValue("Alice", out int aliceScore))
{
    Console.WriteLine($"Alice: {aliceScore}");
}

// 覆盖已有值
scores["Alice"] = 92;

// 按键排序顺序遍历
foreach (KeyValuePair<string, int> item in scores)
{
    Console.WriteLine($"{item.Key} = {item.Value}");
}

// 删除
scores.Remove("Bob");
scores.RemoveAt(0);

遍历 SortedList 时，可以用 foreach 直接迭代 KeyValuePair<TKey,TValue>，顺序就是键的排序顺序，而不是插入顺序。如果只关心键或值，也可以遍历 Keys 和 Values 两个集合。需要注意 Keys 返回的是动态视图，原集合变化后它也会同步变化，不是复制出来的快照。

删除操作可以使用 Remove(key) 按键删除，也可以使用 RemoveAt(index) 按当前排序位置删除。对于已有排序结果的场景，RemoveAt 有时能省去一次键查找。清空则使用 Clear。

三、自定义排序：降序和自定义键

SortedList 默认使用 Comparer<TKey>.Default 来决定键的大小关系。对于 string 键，默认是区分大小写的升序；对于自定义类型，默认比较器要求类型实现 IComparable<T> 或 IComparable<TKey> 接口。如果没有实现，创建集合不会立即报错，但在插入第一个元素时可能出现 InvalidOperationException，因为找不到有效比较器。

如果需要降序排列，可以在构造函数中传入自定义比较器。下面用 Comparer<string>.Create 生成一个字符串降序比较器。这个方式比单独实现比较器接口更简洁。

using System;
using System.Collections.Generic;

// 创建降序排列的 SortedList
var scoresDesc = new SortedList<string, int>(
    Comparer<string>.Create((x, y) => y.CompareTo(x))
);

scoresDesc.Add("Alice", 90);
scoresDesc.Add("Bob", 85);
scoresDesc.Add("Cindy", 95);

foreach (KeyValuePair<string, int> item in scoresDesc)
{
    Console.WriteLine($"{item.Key} = {item.Value}");
}
// 输出顺序：Cindy、Bob、Alice

需要特别强调的是，SortedList 的排序依据只取决于键。也就是说，当键的比较结果相同，SortedList 会视为重复键并拒绝添加。对于复杂键类型，务必让比较逻辑与业务上的唯一性判断保持一致，否则可能出现两个业务上不同的键因为比较结果相同而无法同时存入。

另外，键一旦存入集合后，不应再修改会影响比较结果的那些字段或属性。因为内部数组已经按旧值排序，修改键内容不会触发重新排序，后续查询可能出现找不到、顺序错乱或重复判断异常等问题。正确做法是移除旧项，再以新键重新添加。

四、和 Dictionary、SortedDictionary 的边界

Dictionary<TKey,TValue> 是哈希表结构，单次读取接近 O(1)，但遍历时无序。SortedDictionary<TKey,TValue> 使用红黑树，插入、删除和读取都是 O(log n)，并且能保持键排序，但节点对象多，内存占用高。SortedList 则介于两者之间：读取 O(log n)，插入删除 O(n)，但内部是连续数组，内存更紧凑。

从实用角度看，如果只需要按键快速查找且不关心顺序，应该选 Dictionary。如果需要按键排序输出，同时数据在初始化阶段批量写入、之后很少改动，SortedList 的内存和遍历性能通常优于 SortedDictionary。如果集合在运行期会频繁增删，SortedDictionary 的 O(log n) 写入会明显更稳定。

还有一个容易忽略的细节：如果插入的数据本身已经排好序，并且总是从尾部追加，SortedList 的写入开销会远低于随机插入。因为二分查找后不需要移动任何元素，只需做一次数组尾部写入。所以批量加载有序数据时，SortedList 的实际表现往往比理论 O(n) 看起来更好。

五、常见问题解答汇总

问题一：SortedList 支持按下标访问吗？

SortedList 本身不可以直接通过整数下标访问元素，但它的 Keys 和 Values 属性返回 IList<TKey> 和 IList<TValue>，可以通过下标获取排序后的第 n 个键或值。例如 scores.Keys[0] 返回排序后第一个键。注意这个下标顺序由键比较器决定，不是插入顺序。

问题二：如何让 SortedList 按键降序排列？

降序排列需要从比较器入手。可以直接在构造函数中传入 Comparer<TKey>.Create 生成的比较器，也可以实现一个完整的 IComparer<TKey>。比较器返回相反的比较结果，就能改变整个集合的排序方向。

问题三：为什么 foreach 遍历时删除会报错？

SortedList 内部维护一个版本号，任何修改操作都会让版本号增加。foreach 迭代器在每次 MoveNext 时检查版本号，一旦发现变化就抛出 InvalidOperationException。安全做法是先复制键列表再遍历删除，或者使用反向循环调用 RemoveAt。

using System;
using System.Collections.Generic;

var list = new SortedList<string, int>();
list.Add("temp_1", 1);
list.Add("keep_1", 2);
list.Add("temp_2", 3);

// 反向移除符合条件的项
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list.Keys[i].StartsWith("temp"))
    {
        list.RemoveAt(i);
    }
}

问题四：键可以为 null 吗？

泛型 SortedList<TKey,TValue> 不允许 null 键。即使 TKey 是引用类型，传入 null 也会抛出 ArgumentNullException。值可以为 null，取决于 TValue 类型。如果需要 null 键的排序场景，应使用其他集合或自定义包装键。

问题五：ContainsKey 和 TryGetValue 应该用哪个？

ContainsKey 用来判断存在，但取得值还需要再次索引查找。TryGetValue 可以在一次查找中同时完成判断和取值，推荐在不确定键是否存在时使用。它既能避免重复查找，也能避免因为键不存在而抛出异常。

问题六：IndexOfKey 和 IndexOfValue 有什么用？

IndexOfKey 返回某个键在排序后的 Keys 数组中的位置，未找到返回 -1。IndexOfValue 在所有值中线性查找，返回第一个匹配位置。值查找是 O(n) 线性扫描，不是二分查找，因此如果频繁按值查找，SortedList 不是理想结构。

C# SortedList排序列表键值对集合修改时间：2026-10-05 19:02:58