When is a List not a List?

  • Article

The answer: When it is a SortedList.

Here is one issue that I have with the Framework.  The name SortedList<T> implies that the class inherits IList<T>, but it does not.  In fact, it implements IDictionary<TKey,TValue>.

This issue came up lately in a project I was working on.  Say you want to enter the integers 1, 4, 4, 7, 7, 9, 15 in a list and have them sorted automatically.  The first instinct would be to use the SortedList<T> collection.  However, this is not a viable option.  Since the collection implements IDictionary, a KeyValuePair is required and the Key values must be unique.  This means that you have to come up with some method of assigning arbitrary Key for each Value that you insert that might be a duplicate. 

Here is what the documentation says concerning the difference between SortedList and SortedDictionary:

  • You can perform index-based retrieval using a SortedList
  • For a SortedList, insertion and removal are generally O(n); however, insertion is O(1) for data that are already in sort order, so that each element is added to the end of the list. (This assumes that a resize is not required.)  For a SortedDictionary, insertion and retrieval are O(log n).
  • A SortedList used less memory than a SortedDictionary.

So basically, they should have named SortedList something more like MoreEfficientSortedDictionary or FasterSortedDictionary. 

Now we could just use a list/array and call the sort method, or create a new collection that calls sort method after every add/insert, but this would not be a very efficient sort.

Thankfully, someone else has already created a complete suite of collections that were not included in the Framework.  The Wintellect Power Collections are a compilation of useful collections that fill that gap.  This library contains an OrderedBag<T> collection that acts as a true sorted list.  Underneath the covers, this collection uses a red-black tree data structure to perform efficient sorting of the list contents.  I have found many of the collections from the library useful (such as Deque<T>), and thought that I would pass it along.