This may appear to be a duplicate of this question, which asks "What’s the difference between SortedList and SortedDictionary?" Unfortunately, the answers do nothing more than quote the MSDN documentation (which clearly states that there are performance and memory use differences between the two) but don't actually answer the question.
In fact (and so this question doesn't get the same answers), according to MSDN:
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 the
SortedDictionary<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) for
SortedList<TKey, TValue>
.If the list is populated all at once
from sorted data,SortedList<TKey,
is faster than
TValue>
SortedDictionary<TKey, TValue>
.
So, clearly this would indicated that SortedList<TKey, TValue>
is the better choice unless you need faster insert and remove operations for unsorted data.
The question still remains, given the information above what are the practical (real-world, business case, etc.) reasons for using a SortedDictionary<TKey, TValue>
? Based on the performance information, it would imply that there really is no need to have SortedDictionary<TKey, TValue>
at all.
Best Answer
I'm not sure how accurate the MSDN documentation is on
SortedList
andSortedDictionary
. It seems to be saying both are implemented using a binary search tree. But if the SortedList uses a binary search tree, why would it be much slower on additions thanSortedDictionary
?Anyway, here are some performance test results.
Each test operates on a
SortedList
/SortedDictionary
containing 10,000 int32 keys. Each test is repeated 1,000 times (Release build, Start without Debugging).The first group of tests add keys in sequence from 0 to 9,999. The second group of tests add random shuffled keys between 0 to 9,999 (every number is added exactly once).
As with any profiling, the important thing is the relative performance, not the actual numbers.
As you can see, on sorted data the sorted list is faster than the
SortedDictionary
. On unsorted data theSortedList
is slightly quicker on retrieval, but about 9 times slower on adding.If both are using binary trees internally, it is quite surprising that the Add operation on unsorted data is so much slower for
SortedList
. It is possible that sorted list may also be adding items to a sorted linear data structure at the same time, which would slow it down.However, you would expect the memory usage of a
SortedList
to be equal or greater than or at least equal to aSortedDictionary
. But this contradicts what the MSDN documentation says.