Why is there no SortedList in .NET? [closed]

Although nobody can really tell you why there is no SortedList<T>, it is possible to discuss why SortedList takes a key and a value. A dictionary maps keys to values. The typical ways to do this are with a binary tree, a hash table, and a list (array), though hash tables are most common because they are O(1) for most operations.

The primary operation that it doesn’t support in O(1) is getting the next key in order. If you want to be able to do that, you typically use a binary tree, giving you a sorted dictionary.

If you decide to implement the map as a list, you would keep the elements sorted by key so that lookup is O(lg n), giving you another sorted dictionary — in the form of a sorted list. Of course the name SortedDictionary was already taken, but SortedList wasn’t. I might have called it SortedListDictionary or SortedDictionaryList, but I didn’t get to name it.

Leave a Comment