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:

1: static void Main(string[] args)
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:

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

Tags :

23 Responses to “Why SortedList<Key,Val> Is Useless”


  1. Greg Beech

    Said on July 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.

  2. gm

    Said on July 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.

  3. TImothy Bland

    Said on July 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.

  4. Brendan Forster

    Said on July 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.”

  5. Amit

    Said on July 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.

  6. Stefan

    Said on July 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.

  7. JV

    Said on July 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.

  8. AlexR

    Said on July 3, 2008 :

    If you need access to items by index, you need SortedList.

  9. Juan C. Olivares

    Said on July 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.

  10. Wesner Moise

    Said on July 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.

  11. James

    Said on July 3, 2008 :

    Sometimes performance and memory utilization does matter…so I wouldn’t call SortedList useless…

  12. Amit

    Said on July 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.

  13. Jeff

    Said on July 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.

  14. Matthew Vines

    Said on July 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.

  15. Amit

    Said on July 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 :)

  16. fschwiet

    Said on October 4, 2008 :

    Here’s something write about that I’d be interested in: Is there an alternative to SortedList that allows duplicate keys?

  17. Morlack

    Said on September 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

  18. Julia

    Said on January 7, 2010 :

    When I saw Sorted List, I thought this is totally what I need. Just after started to use it, I noticed that the list cannot be in reverse order. What I need is the latest items. OK fine, I’ll change my implementation to account for that. Then comes the edge cases while testing. Now I need duplicate keys in the sorted list. I checked msdn hoping there is a property to set on the list (or a different contructor with an owerrite option) to allow duplicate keys. Nope there isn’t. I wish I’ve written the list myself instead of using sorted list. I would have spent less time for sure.

  19. Colin Clark

    Said on February 3, 2010 :

    No, it really is a crappy name. The base name of List indicates that it should have at least some basic characteristics of a List- not just be a very slightly modified SortedDictionary.

    The MSDN documentation doesn’t say anything about a unique key contraint.

    I just wasted several hours because of SortedList.

  20. Robin Alden

    Said on July 26, 2010 :

    I think what Amit is trying to do makes alot of sense. Forget about the names and memory structures and concentrate on the problem he is trying to solve.

    1. Insert records into a list with a field that is used to sort them.
    2. Choose to allow duplicates (or not).
    3. Enumerate through those records in their sorted order by index.
    4. Achieve maximum performance (perhaps specify which tradeoff is prefered, ie memory or speed).

    I’d also like these features in an out of the box generic object.

  21. Coder

    Said on July 23, 2011 :

    I couldn’t agree more with you Amit.
    Sortedlist seemed the most obvious collection for me to use, but now I understand its totally useless FOR A SORTED LIST of strings that is.

    When list is a list of string, I thought sorted list is just that but sorts the strings when I implement a comparer-method or someting. Wtf I need to insert them with a KEY. Ok fine. WTF exception indeed!

    What I needed was a collection where I can insert strings (without a key obviously), keep them sorted (occording to that string), and be able to retrieve the top n strings, and delete the m strings in this collection.

    Does anyone plz know a collection for me to use for this SORTED LIST OF STINGS that cannot be implemented with SORTED LIST ?

  22. Coder

    Said on July 23, 2011 :

    I couldn’t agree more with you Amit.
    Sortedlist seemed the most obvious collection for me to use, but now I understand its totally useless FOR A SORTED LIST of strings that is.

    When list is a list of string, I thought sorted list is just that but sorts the strings when I implement a comparer-method or someting. Wtf I need to insert them with a KEY. Ok fine. WTF exception indeed!

    What I needed was a collection where I can insert strings (without a key obviously), keep them sorted (occording to that string), and be able to retrieve the top n strings, and delete the last m strings in this collection.

    Does anyone plz know a collection for me to use for this SORTED LIST OF STINGS that cannot be implemented with SORTED LIST ?

1 Trackback(s)

  1. Jul 11, 2008: LIST.SORT(), COMPARER AND ICOMPARABLE | Dev102.com

Post a Comment