已排序的集合类型

System.Collections.SortedList 类、System.Collections.Generic.SortedList<TKey,TValue> 泛型类和 System.Collections.Generic.SortedDictionary<TKey,TValue> 泛型类与 Hashtable 类和 Dictionary<TKey,TValue> 泛型类的相似之处在于均实现 IDictionary 接口，不同之处在于它们让元素一直按键的排序顺序排列，并且不具备哈希表的 O(1) 插入和检索特性。 这三个类具有若干共性：

• 这三个类全都实现 System.Collections.IDictionary 接口。 两个泛型类还实现 System.Collections.Generic.IDictionary<TKey,TValue> 泛型接口。

• 每个元素都是用于枚举的键/值对。

  注意

  枚举时，非泛型 SortedList 类返回 DictionaryEntry 对象，尽管两个泛型类型返回 KeyValuePair<TKey,TValue> 对象。

• 元素按 System.Collections.IComparer 实现代码（对于非泛型 SortedList）或 System.Collections.Generic.IComparer<T> 实现代码（对于两个泛型类）进行排序。

• 每个类提供了返回仅包含键或仅包含值的集合的属性。

下表列出了两个已排序列表类与 SortedDictionary<TKey,TValue> 类之间的一些区别。

SortedList 非泛型类和 SortedList<TKey,TValue> 泛型类	SortedDictionary<TKey,TValue> 泛型类
返回键和值的属性是有索引的，从而允许高效的索引检索。	无索引的检索。
检索属于 O(log n) 操作。	检索属于 O(log n) 操作。
插入和删除通常属于 O(n) 操作；不过，对于已按排序顺序排列的数据，插入属于 O(log n) 操作，这样每个元素都可以添加到列表的末尾。 （这假设不需要调整大小。）	插入和删除属于 O(log n) 操作。
比 SortedDictionary<TKey,TValue> 使用更少的内存。	比 SortedList 非泛型类和 SortedList<TKey,TValue> 泛型类使用更多内存。

对于必须可通过多个线程并发访问的已排序列表或字典，可以向派生自 ConcurrentDictionary<TKey,TValue> 的类添加排序逻辑。 考虑不可变性时，以下相应的不可变类型遵循类似的排序语义：ImmutableSortedSet<T> 和 ImmutableSortedDictionary<TKey,TValue>。

注意

对于包含自己的键的值（例如，包含雇员 ID 编号的雇员记录），可以通过派生自 KeyedCollection<TKey,TItem> 泛型类，创建具有列表和字典的某些特性的键控集合。

从 .NET Framework 4 开始，SortedSet<T> 类提供在执行插入、删除和搜索操作之后让数据一直按排序顺序排列的自平衡树。 此类和 HashSet<T> 类实现 ISet<T> 接口。

请参阅

• System.Collections.IDictionary
• System.Collections.Generic.IDictionary<TKey,TValue>
• ConcurrentDictionary<TKey,TValue>
• 常用的集合类型