C# SortedDictionary以及SortedList的浅谈

　　

msdn叙述：
the sorteddictionary<tkey, tvalue> 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<tkey, tvalue> 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<tkey, tvalue> uses less memory than sorteddictionary<tkey,
tvalue>.

sorteddictionary<tkey, tvalue> has faster insertion and removal operations for unsorted data, o(log n) as opposed to o(n) for sortedlist<tkey, tvalue>.

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

两者基本叙述：
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://*.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary
https://*.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue