C# SortedDictionary以及SortedList的浅谈

标签：diff   class   sse   between   obj   msdn   opp   alt   二分查找   

msdn叙述：
The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedList generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

SortedList uses less memory than SortedDictionary TValue>.

SortedDictionary has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList.

If the list is populated all at once from sorted data, SortedList TValue> is faster than SortedDictionary.
译文：
SortedDictionary泛型类是检索O(log n)的二叉搜索树，其中n是字典中的元素数。在这里，它类似于SortedList泛型类。这两个类有相似的对象模型，并且都有O(log n)检索。这两个类的不同之处在于内存的使用以及插入和删除的速度:
SortedList比SortedDictionary使用更少的内存.
SortedDictionary对于未排序的数据O(log n)具有更快的插入和删除操作，而SortedList的插入和删除都是O(n)
如果列表是由已排序的数据一次填充的，那么SortedList要比SortedDictionary快。

两者基本叙述：
SortedList：是一个已序的数组（基于KeyValuePair的数组）。基于键值排序的键值对数组，使用二分查找(log n)检索key，也可根据index检索(log 1)，add和remove都是o(n)。SortedList为了保持数组的排序，它会移动位于插入的元素位置之后的所有元素（使用Array.Copy()）,由于每次的插入都会重新排序，导致插入时的性能很差，因此并不推荐使用SortedList排序一个数组。

SortedDictionary: 是一个BST，基于二叉查找树实现，使用二分查找检索(key)，add和remove都是o(log n)

两者性能比较：

两者实现比较：

参考：
https://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary
https://stackoverflow.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue

C# SortedDictionary以及SortedList的浅谈

标签：diff   class   sse   between   obj   msdn   opp   alt   二分查找   

原文地址：https://www.cnblogs.com/zhiyong-ITNote/p/10323632.html