The other day I wan in the need of a sorted collection. I found that there are 2 sorted collections available. SortedDictionary and SortedList. Now let me ask you, what do you think is the difference? Well, my first though was that they are the same except for the keys, which in SortedDictionary have to be unique.
Check out this code:
2: {
3: SortedList<int, string> list = new SortedList<int, string>();
4: list.Add(1, “one”);
5: list.Add(1, “two”);
6: foreach (string s in list.Values)
7: {
8: Console.WriteLine(s);
9: }
10:}
What do you think will be the output?
I thought that It will be:
one
two
I also thought that because the keys are the same you might also get the reversed order:
two
one
It seems I was wrong on both my guesses…
The answer is that you will get an ArgumentException exception on line 5 that says : An entry with the same key already exists. WTF!!!!!
Then what is the difference between SortedList and SortedDictionary, a quick search got me to this page: http://msdn.microsoft.com/en-us/library/f7fta44c.aspx and I quote:
The SortedDictionary<(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 respect, it is similar to the SortedList<(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>)>).
Basically what it says is that they are the same. So what is a SortedList good for? beats me. I deem it Useless. After messing around with it some more I found that you cannot access the values by index, meaning: SortedList[i] will not work. What is it good for then?
What should you do instead? you have 2 other options which I will discuss in my next post
Amit
1 Trackback(s)
- Jul 11, 2008: LIST.SORT(), COMPARER AND ICOMPARABLE | Dev102.com
Write for Dev102!
We pay for user submitted tutorials and articles that we publish. Anyone can send in a contribution
Learn More
Greg Beech Said on Jul 2, 2008 :
It’s not useless - it tells you in the help what it is useful for. If you want to use less memory or your list is created with mostly pre-sorted data then it may be better then SortedDictionary. The names are confusing, but that doesn’t imply uselessness.
gm Said on Jul 2, 2008 :
Did you fail to read the part where you quoted text saying they are different? One is clearly a list and the other a binary tree… Big difference between the two. And yes, the difference matters (why do you consider O(n) the same as O(n log n) to be the same?).
Algorithms matter.
TImothy Bland Said on Jul 3, 2008 :
Actually what is says is that the SortedList uses less memory… what is complicated about that? Time vs. memory is an important tradeoff…. perhaps one that has never been relevant to you.
Brendan Forster Said on Jul 3, 2008 :
The exception is occuring because you have two identical integers as keys. From the MSDN article you linked:
“Every key in a SortedList<(Of )>) must be unique.”
Amit Said on Jul 3, 2008 :
My point was that if you need a list of sorted objects SortedList is really not the way to go.
And that the name selection is absolutly terrible.
If I would have done it I would have Only the SortedDictionary with the option to set some properties and make it like the SortedList.
Stefan Said on Jul 3, 2008 :
While I sure understand the differences and tradeoffs, I’m still on Amits side on this one when it comes to the naming. *intuitively* you think SortedList is just a list since it’s called just that. And to me a “list” should allow duplicates.
JV Said on Jul 3, 2008 :
Nothing WTF about that exception indeed… You are using the same id’s (twice). It should be common sense that when you are using a collection, the key should always be unique. And last, if you implement the proper interfaces SortedList works like a charm on any object.
AlexR Said on Jul 3, 2008 :
If you need access to items by index, you need SortedList.
Juan C. Olivares Said on Jul 3, 2008 :
I think the exception is an expected behavior. You can not define two elements using the same key in the dictionary… that’s exactly what I would expect.
Wesner Moise Said on Jul 3, 2008 :
Your argument regarding Add(key, value) rendering the collection useless is flawed…
Standard dictionary behavior:
Add(key, value) returns an exception if the key already exists
this[key] = value works even if the key already exists
Add is checked, and the indexer is not checked.
James Said on Jul 3, 2008 :
Sometimes performance and memory utilization does matter…so I wouldn’t call SortedList useless…
Amit Said on Jul 3, 2008 :
I though to myself that it is weird that there is a KEY in a List (that was before I checked out the msdn). But I still did not expect an Exception because as I said before, the name totally threw me off. I acctually expected that duplicated “Keys” will be allowed because it was a List and not a Dictionary.
Jeff Said on Jul 7, 2008 :
Amit,
It isn’t useless. I use them quit a bit in my unbound code for storing combobox data of key/value. Its perfect.
Matthew Vines Said on Jul 17, 2008 :
They would have probably done better to allow a flag in an overloaded constructor to determine which implementation to use, (tree or list). And stayed with one name for the public interface. But they just didn’t make that decision.
Amit Said on Jul 17, 2008 :
@Matthew
Great idea! I really like it, it would have made things alot clearer, but then I would have no post to write
fschwiet Said on Oct 4, 2008 :
Here’s something write about that I’d be interested in: Is there an alternative to SortedList that allows duplicate keys?
Morlack Said on Sep 23, 2009 :
This is a old post..but maybe will be useful for googlers :
SortedList Vs SortedDictionary : 1 - 0
http://msdn.microsoft.com/en-us/library/5z658b67.aspx