何时使用 SortedList 而不是 SortedDictionary？

这可能看起来与此重复question https://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary，它询问“有什么区别排序列表 http://msdn.microsoft.com/en-us/library/ms132319.aspx and 排序字典 http://msdn.microsoft.com/es-mx/library/f7fta44c.aspx？”不幸的是，答案只不过是引用了 MSDN 文档（其中明确指出两者之间存在性能和内存使用差异），但实际上并没有回答问题。

事实上（所以这个问题没有得到相同的答案），根据 MSDN：

The SortedList<TKey, TValue>通用的 class 是一个二叉搜索树 O(log n) 检索，其中 n 是 字典中的元素数量。 在这一点上，它类似于SortedDictionary<TKey, TValue>通用的 班级。两个类有相似之处 对象模型，并且都有 O(log n) 恢复。两个班级在哪里 不同之处在于内存使用和速度 插入和移除：

• SortedList<TKey, TValue>使用较少 记忆比SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>有 更快的插入和移除 对未排序数据的操作，O(log n) 与 O(n) 相反SortedList<TKey, TValue>.

• 如果列表一次全部填充 从排序数据中，SortedList<TKey, TValue>比SortedDictionary<TKey, TValue>.

所以，显然这表明SortedList<TKey, TValue>是更好的选择unless您需要更快的插入和删除操作unsorted data.

考虑到上述信息，问题仍然存在：使用SortedDictionary<TKey, TValue>？根据性能信息，这意味着确实没有必要SortedDictionary<TKey, TValue> at all.

我不确定 MSDN 文档的准确性如何SortedList and SortedDictionary。似乎是说两者都是使用二叉搜索树实现的。但如果 SortedList 使用二叉搜索树，为什么它的添加速度会比SortedDictionary?

无论如何，这是一些性能测试结果。

每个测试都运行在SortedList / SortedDictionary包含 10,000 个 int32 键。每个测试重复 1,000 次（发布构建、启动而不调试）。

第一组测试按从 0 到 9,999 的顺序添加密钥。第二组测试添加 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

与任何分析一样，重要的是相对性能，而不是实际数字。

正如您所看到的，在排序数据上，排序列表比排序列表更快SortedDictionary。对于未排序的数据SortedList检索时稍快一些，但添加时慢约 9 倍。

如果两者都在内部使用二叉树，那么对未排序数据的 Add 操作会慢得多，这是非常令人惊讶的。SortedList。排序列表也可能同时向排序线性数据结构添加项目，这会减慢速度。

但是，您可能期望的内存使用量是SortedList等于或大于或至少等于SortedDictionary。但这与 MSDN 文档所说的相矛盾。