SortedList 泛型类是具有 O(log n) 检索的二进制搜索树,其中 n 是字典中元素的数目。就这一点而言,它与 SortedDictionary 泛型类相似。这两个类具有相似的对象模型,并且都具有 O(log n) 的检索运算复杂度。这两个类的区别在于内存的使用以及插入和移除元素的速度:
-
SortedList 使用的内存比 SortedDictionary 少。
-
SortedDictionary 可对未排序的数据执行更快的插入和移除操作,它的运算复杂度为 O(log n),而 SortedList 的运算复杂度为 O(n)。
-
如果使用排序数据一次性填充列表,则 SortedList 比 SortedDictionary 快。
SortedDictionary 类和 SortedList 类之间的另一个区别是:SortedList 支持通过由 Keys 和 Values 属性返回的集合对键和值执行高效的索引检索。访问此属性时无需重新生成列表,因为列表只是键和值的内部数组的包装。下面的代码演示如何使用 Values 属性从已排序的字符串列表中按索引检索值:
Dim v As String = mySortedList.Values(3)
string v = mySortedList.Values[3];
String^ v = mySortedList->Values[3];
SortedList 作为键/值对的数组来实现,它按键排序。每个元素都可以作为一个 KeyValuePair 对象进行检索。
只要键对象用作 SortedList 中的键,它们就必须是永远不变的。SortedList 中的每个键必须是唯一的。键不能为 空引用(在 Visual Basic 中为 Nothing),但如果列表中值的类型 TValue 为引用类型,则值可以。
SortedList 需要比较器实现来排序和执行比较。默认比较器 Comparer.Default 检查键类型 TKey 是否实现 System.IComparable 以及是否使用该实现(如果可用)。否则,Comparer.Default 将检查键类型 TKey 是否实现 System.IComparable。如果键类型 TKey 未实现任一接口,则您可以在构造函数重载中指定一个接受 comparer 参数的 System.Collections.Generic.IComparer 实现。
SortedList 的容量是指 SortedList 可以保存的元素数。在此实现中,SortedList 的默认初始容量为 16;但该默认值可能在 .NET Framework 的未来版本中更改。向 SortedList 添加元素时,将通过重新分配内部数组,根据需要自动增大容量。可通过调用 TrimExcess 或通过显式设置 Capacity 属性减少容量。减少容量会重新分配内存并复制 SortedList 中的所有元素。
C# 语言中的 foreach 语句(在 C++ 中为 for each,在 Visual Basic 中为 For Each)需要集合中的元素类型。由于 SortedList 的元素是键/值对,因此元素类型既不是键的类型,也不是值的类型。而是 KeyValuePair 类型。例如:
foreach (KeyValuePair<int, string> kvp in mySortedList) {...}
for each (KeyValuePair<int, String^> kvp in mySortedList) {...}
For Each kvp As KeyValuePair(Of Integer, String) In mySortedList
...
Next kvp
foreach 语句是对枚举数的包装,它只允许从集合中读取,不允许写入集合。