Is there any real practical difference between a SortedList<TKey,TValue>
and a SortedDictionary<TKey,TValue>
? Are there any circumstances where you would specifically use one and not the other?
Yes - their performance characteristics differ significantly. It would probably be better to call them SortedList
and SortedTree
as that reflects the implementation more closely.
Look at the MSDN docs for each of them (SortedList
, SortedDictionary
) for details of the performance for different operations in different situtations. Here's a nice summary (from the SortedDictionary
docs):
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 theSortedList<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 thanSortedDictionary<TKey, TValue>
.
SortedDictionary<TKey, TValue>
has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) forSortedList<TKey, TValue>
.If the list is populated all at once from sorted data,
SortedList<TKey, TValue>
is faster thanSortedDictionary<TKey, TValue>
.
(SortedList
actually maintains a sorted array, rather than using a tree. It still uses binary search to find elements.)