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
By Greg Beech on Jul 2, 2008 | Reply
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.
By gm on Jul 2, 2008 | Reply
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.
By TImothy Bland on Jul 3, 2008 | Reply
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.
By Brendan Forster on Jul 3, 2008 | Reply
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.”
By Amit on Jul 3, 2008 | Reply
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.
By Stefan on Jul 3, 2008 | Reply
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.
By JV on Jul 3, 2008 | Reply
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.
By AlexR on Jul 3, 2008 | Reply
If you need access to items by index, you need SortedList.
By Juan C. Olivares on Jul 3, 2008 | Reply
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.
By Wesner Moise on Jul 3, 2008 | Reply
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.
By James on Jul 3, 2008 | Reply
Sometimes performance and memory utilization does matter…so I wouldn’t call SortedList useless…
By Amit on Jul 3, 2008 | Reply
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.
By Jeff on Jul 7, 2008 | Reply
Amit,
It isn’t useless. I use them quit a bit in my unbound code for storing combobox data of key/value. Its perfect.
By Matthew Vines on Jul 17, 2008 | Reply
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.
By Amit on Jul 17, 2008 | Reply
@Matthew
Great idea! I really like it, it would have made things alot clearer, but then I would have no post to write