Maybe a silly question, but is there any real practical difference between a SortedList
and a SortedDictionary
? Are there any circumstances where you would specifically use one and not the other?
views:
1185answers:
2Yes - 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
SortedList<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 theSortedDictionary<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>
.
Check out the MSDN page for SortedList:
From Remarks section:
The
SortedList<(Of <(TKey, TValue>)>)
generic class is a binary search tree withO(log n)
retrieval, wheren
is the number of elements in the dictionary. In this, it is similar to theSortedDictionary<(Of <(TKey, TValue>)>)
generic class. The two classes have similar object models, and both haveO(log n)
retrieval. Where the two classes differ is in memory use and speed of insertion and removal:
SortedList<(Of <(TKey, TValue>)>)
uses less memory thanSortedDictionary<(Of <(TKey, TValue>)>)
.
SortedDictionary<(Of <(TKey, TValue>)>)
has faster insertion and removal operations for unsorted data,O(log n)
as opposed toO(n)
forSortedList<(Of <(TKey, TValue>)>)
.If the list is populated all at once from sorted data,
SortedList<(Of <(TKey, TValue>)>)
is faster thanSortedDictionary<(Of <(TKey, TValue>)>)
.