c# - SortedList 和 SortedDictionary 之间有什么区别？

Question

SortedList<TKey,TValue> 之间有什么真正的实际区别吗？和一个 SortedDictionary<TKey,TValue> ？在某些情况下，您会特别使用其中一种而不使用另一种吗？

Answer 1

是的——它们的性能特征差异很大。称它们为 SortedList 可能会更好和 SortedTree因为这更密切地反射(reflect)了实现。

查看它们各自的 MSDN 文档( SortedList 、 SortedDictionary )，了解不同情况下不同操作的性能详细信息。这是一个很好的总结(来自 SortedDictionary 文档):

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>.

(SortedList实际上维护的是一个排序数组，而不是使用树。它仍然使用二进制搜索来查找元素。)