已排序的集合类型Sorted Collection Types

System.Collections.SortedList 类、System.Collections.Generic.SortedList<TKey,TValue> 泛型类和 System.Collections.Generic.SortedDictionary<TKey,TValue> 泛型类与 Hashtable 类和 Dictionary<TKey,TValue> 泛型类的相似之处在于均实现 IDictionary 接口,不同之处在于它们让元素一直按键的排序顺序排列,并且不具备哈希表的 O(1) 插入和检索特性。The System.Collections.SortedList class, the System.Collections.Generic.SortedList<TKey,TValue> generic class, and the System.Collections.Generic.SortedDictionary<TKey,TValue> generic class are similar to the Hashtable class and the Dictionary<TKey,TValue> generic class in that they implement the IDictionary interface, but they maintain their elements in sort order by key, and they do not have the O(1) insertion and retrieval characteristic of hash tables. 这三个类具有若干共性:The three classes have several features in common:

下表列出了两个已排序列表类与 SortedDictionary<TKey,TValue> 类之间的一些区别。The following table lists some of the differences between the two sorted list classes and the SortedDictionary<TKey,TValue> class.

SortedList 非泛型类和 SortedList<TKey,TValue> 泛型类SortedList nongeneric class and SortedList<TKey,TValue> generic class SortedDictionary<TKey,TValue> 泛型类SortedDictionary<TKey,TValue> generic class
返回键和值的属性是有索引的,从而允许高效的索引检索。The properties that return keys and values are indexed, allowing efficient indexed retrieval. 无索引的检索。No indexed retrieval.
检索属于 O(log n) 操作。Retrieval is O(log n). 检索属于 O(log n) 操作。Retrieval is O(log n).
插入和删除通常属于 O(n) 操作;不过,对于已按排序顺序排列的数据,插入属于 O(log n) 操作,这样每个元素都可以添加到列表的末尾。Insertion and removal are generally O(n); however, insertion is O(log n) for data that are already in sort order, so that each element is added to the end of the list. (这假设不需要调整大小。)(This assumes that a resize is not required.) 插入和删除属于 O(log n) 操作。Insertion and removal are O(log n).
SortedDictionary<TKey,TValue> 使用更少的内存。Uses less memory than a SortedDictionary<TKey,TValue>. SortedList 非泛型类和 SortedList<TKey,TValue> 泛型类使用更多内存。Uses more memory than the SortedList nongeneric class and the SortedList<TKey,TValue> generic class.

对于必须可通过多个线程并发访问的已排序列表或字典,可以向派生自 ConcurrentDictionary<TKey,TValue> 的类添加排序逻辑。For sorted lists or dictionaries that must be accessible concurrently from multiple threads, you can add sorting logic to a class that derives from ConcurrentDictionary<TKey,TValue>.

备注

对于包含自己的键的值(例如,包含雇员 ID 编号的雇员记录),可以通过派生自 KeyedCollection<TKey,TItem> 泛型类,创建具有列表和字典的某些特性的键控集合。For values that contain their own keys (for example, employee records that contain an employee ID number), you can create a keyed collection that has some characteristics of a list and some characteristics of a dictionary by deriving from the KeyedCollection<TKey,TItem> generic class.

从 .NET Framework 4 开始,SortedSet<T> 类提供在执行插入、删除和搜索操作之后让数据一直按排序顺序排列的自平衡树。Starting with the .NET Framework 4, the SortedSet<T> class provides a self-balancing tree that maintains data in sorted order after insertions, deletions, and searches. 此类和 HashSet<T> 类实现 ISet<T> 接口。This class and the HashSet<T> class implement the ISet<T> interface.

请参阅See also