tags:

views:

1185

answers:

2

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?

+10  A: 

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

Jon Skeet
How did you get that to format correctly? I'm still trying to figure out the formatting and as you can see mine didn't look nearly as nice as yours.
Stephan
*snickers* - "...mine didn't look nearly as nice as yours". :P
Cerebrus
Thanks v much to all for the pointers. I guess I'm just too lazy to RTFM... much easier to ask the nice folks on SO... ;) I voted you both up for the answers; Jon gets answer credit for being first on the trigger. :)
Shaul
+4  A: 

Check out the MSDN page for SortedList:

From Remarks section:

The SortedList<(Of <(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<(Of <(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<(Of <(TKey, TValue>)>) uses less memory than SortedDictionary<(Of <(TKey, TValue>)>).
  • SortedDictionary<(Of <(TKey, TValue>)>) has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<(Of <(TKey, TValue>)>).

  • If the list is populated all at once from sorted data, SortedList<(Of <(TKey, TValue>)>) is faster than SortedDictionary<(Of <(TKey, TValue>)>).

Stephan
@Stephan: Formatted your post and moved the link inline. +1 ;-)
Cerebrus