何时通过SortedDictionary <TKey，TValue>使用SortedList <TKey，TValue>？
这似乎是这个问题的重复，它询问“ SortedList和SortedDictionary有什么区别？” 不幸的是，答案只不过是引用MSDN文档（明确指出两者之间存在性能和内存使用差异），但实际上并没有回答这个问题。
事实上（所以这个问题没有得到相同的答案），根据MSDN：
SortedList<TKey, TValue>generics类是一个O（log n）检索的二叉search树，其中n是字典中元素的数量。 在这里，它类似于SortedDictionary<TKey, TValue>generics类。 这两个类有相似的对象模型，都有O（log n）检索。 这两个类别在内存使用和插入和删除速度方面存在差异：
SortedList<TKey, TValue>使用的内存less于SortedDictionary<TKey, TValue>。
SortedDictionary<TKey, TValue>对未sorting的数据有更快的插入和删除操作，O（log n）与SortedList<TKey, TValue>O（n）相对。如果列表从已sorting的数据一次全部填充，则
SortedList<TKey, TValue>比SortedDictionary<TKey, TValue>快。
所以，显然这表明SortedList<TKey, TValue>是更好的select， 除非您需要更快地插入和删除未sorting数据的操作。
问题仍然存在，鉴于上面的信息是什么使用SortedDictionary<TKey, TValue>的实际（真实世界，商业案例等）原因？ 根据性能信息，这意味着根本不需要有SortedDictionary<TKey, TValue> 。
我不确定MSDN文档在SortedList和SortedDictionary上有多准确。 这似乎是说这两个都是使用二叉search树实现的。 但是，如果SortedList使用二叉search树，那么为什么添加比SortedDictionary慢？
无论如何，这里有一些性能testing结果。
每个testing对包含10,000个int32键的SortedList / SortedDictionary进行操作。 每个testing重复1.000次（发布版本，开始不debugging）。
第一组testing按顺序从0增加到9,999。 第二组testing添加0到9,999之间的随机混洗密钥（每个数字只加一次）。
***** Tests.PerformanceTests.SortedTest SortedDictionary Add sorted: 4411 ms SortedDictionary Get sorted: 2374 ms SortedList Add sorted: 1422 ms SortedList Get sorted: 1843 ms ***** Tests.PerformanceTests.UnsortedTest SortedDictionary Add unsorted: 4640 ms SortedDictionary Get unsorted: 2903 ms SortedList Add unsorted: 36559 ms SortedList Get unsorted: 2243 ms
至于任何分析，重要的是相对的performance，而不是实际的数字。
正如你所看到的，在sorting数据上，sorting列表比SortedDictionary快。 在未sorting的数据上， SortedList检索速度稍微快一些，但是添加速度要慢9倍左右。
如果两者都在内部使用二叉树，那么令人惊讶的是对未sorting数据的Add操作对于SortedList来说太慢了。 sorting列表也可能是同时向sorting后的线性数据结构添加项目，这会降低速度。
但是，您会希望SortedList的内存使用量等于或大于或等于SortedDictionary 。 但是这与MSDN文档所说的相矛盾。
我不知道为什么MSDN说SortedList<TKey, TValue>使用二叉树来实现它，因为如果你看看像Reflector这样的反编译Reflector代码，你会意识到它不是真的。
SortedList<TKey, TValue>只是一个随着时间而增长的数组。
每次插入元素时，首先检查数组是否具有足够的容量，如果不是，则重新创build一个更大的数组，并将旧元素复制到其中（如List<T> ）
之后，它使用二进制search来search插入元素的位置（这是可能的，因为该数组是可索引的并且已经sorting）。
为了保持数组的sorting，它将移动（或推）位于要插入元素位置之后的所有元素 （使用Array.Copy() ）。
例如：
// we want to insert "3" 2 4 <= 3 5 8 9 . . . // we have to move some elements first 2 . <= 3 4 5 | 8 v 9 . .
这就解释了为什么当插入未sorting的元素时， SortedList性能如此糟糕。 它必须重新复制一些元素几乎每一个插入。 唯一的情况是不得不在数组的末尾插入元素。
SortedDictionary<TKey, TValue>是不同的，并使用二叉树来插入和检索元素。 它也有插入的成本，因为有时树需要重新平衡（但不是每插入）。
使用SortedList或SortedDictionarysearch元素时，性能非常相似，因为它们都使用二分search。
在我看来，你不应该使用SortedList来sorting数组。 除非有很less的元素，否则将值插入到列表（或数组）中然后调用Sort()方法将会更快。
当你有一个已经sortingSortedList值的列表（例如：从数据库）时， SortedList是非常有用的，你想保持它的sorting并执行一些操作，以便利用sorting（例如： SortedList Contains()方法执行二分查找而不是线性search）
SortedDictionary提供了与SortedList相同的优点，但如果要插入的值尚未sorting，则执行效果会更好。
编辑：如果您使用的是.NET Framework 4.5， SortedDictionary<TKey, TValue>的替代项是SortedSet<T> 。 它和SortedDictionary ，使用二叉树，但是键和值在这里是一样的。
它们是为了两个不同的目的吗？
这两个集合types在.NET中没有太多的语义差异。 它们都提供了键控查找，并按照键的顺序保存条目。 在大多数情况下，你会对其中的任何一个都行。 也许唯一的区别是SortedList允许的索引检索。
但是performance呢？
但是，性能差异可能是select它们之间更强的因素。 以下是它们渐近复杂性的表格视图。
+------------------+---------+----------+--------+----------+----------+---------+ | Collection | Indexed | Keyed | Value | Addition | Removal | Memory | | | lookup | lookup | lookup | | | | +------------------+---------+----------+--------+----------+----------+---------+ | SortedList | O(1) | O(log n) | O(n) | O(n)* | O(n) | Lesser | | SortedDictionary | n/a | O(log n) | O(n) | O(log n) | O(log n) | Greater | +------------------+---------+----------+--------+----------+----------+---------+ * Insertion is O(1) for data that are already in sort order, so that each element is added to the end of the list (assuming no resize is required).
概要
粗略地说，在下列情况下需要一个SortedList<K, V> ：
- 你需要索引查询。
- 减less内存开销是可取的。
- 你的input数据已经sorting（比如你已经从数据库中订购了）。
在下列情况下，您应该更喜欢SortedDictionary<K, V> ：
- 相对的整体performance很重要（关于缩放）。
- 你的input数据是无序的。
编写代码
SortedList<K, V>和SortedDictionary<K, V>实现了IDictionary<K, V> ，所以在你的代码中你可以从方法返回IDictionary<K, V>或者声明IDictionary<K, V>variables。 基本上隐藏实现细节，并针对接口进行编码。
IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg.
将来，如果您对某个系列的性能特点不满意，可以更容易地进行切换。
有关这两种集合types的更多信息，请参阅链接的原始问题 。
这里的所有都是它的。 键的检索是可比较的，但字典的添加速度要快得多。
我尝试尽可能多地使用SortedList，因为它允许我遍历键和值集合。 就我所知，这对于SortedDictionary是不可能的。
我不知道这一点，但据我所知字典商店数据在树结构，而列表存储数据线性arrays。 这就解释了为什么插入和删除字典更快，因为更less的内存需要转移。 这也解释了为什么你可以遍历SortedLists而不是SortedDictionary。
性能差异的可视化表示。
