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

Question

Why is there only a SortedList<TKey, TValue> which looks more like a dictionary, but no SortedList<T> that is actually just a list that is always sorted?

According to the MSDN documentation on SortedList, it is actually internally implemented as a dynamically-sized array of KeyValuePair<TKey, TValue> that is always sorted by the key. Wouldn’t the same class be more useful as a list of any type T? Wouldn’t that fit the name better, too?

Answer 1

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.

Answer 2

There is now :)

public class SortedList<T> : ICollection<T>
{
    private List<T> m_innerList;
    private Comparer<T> m_comparer;

    public SortedList() : this(Comparer<T>.Default)
    {
    }

    public SortedList(Comparer<T> comparer)
    {
        m_innerList = new List<T>();
        m_comparer = comparer;
    }

    public void Add(T item)
    {
        int insertIndex = FindIndexForSortedInsert(m_innerList, m_comparer, item);
        m_innerList.Insert(insertIndex, item);
    }

    public bool Contains(T item)
    {
        return IndexOf(item) != -1;
    }

    /// <summary>
    /// Searches for the specified object and returns the zero-based index of the first occurrence within the entire SortedList<T>
    /// </summary>
    public int IndexOf(T item)
    {
        int insertIndex = FindIndexForSortedInsert(m_innerList, m_comparer, item);
        if (insertIndex == m_innerList.Count)
        {
            return -1;
        }
        if (m_comparer.Compare(item, m_innerList[insertIndex]) == 0)
        {
            int index = insertIndex;
            while (index > 0 && m_comparer.Compare(item, m_innerList[index - 1]) == 0)
            {
                index--;
            }
            return index;
        }
        return -1;
    }

    public bool Remove(T item)
    {
        int index = IndexOf(item);
        if (index >= 0)
        {
            m_innerList.RemoveAt(index);
            return true;
        }
        return false;
    }

    public void RemoveAt(int index)
    {
        m_innerList.RemoveAt(index);
    }

    public void CopyTo(T[] array)
    {
        m_innerList.CopyTo(array);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        m_innerList.CopyTo(array, arrayIndex);
    }

    public void Clear()
    {
        m_innerList.Clear();
    }

    public T this[int index]
    {
        get
        {
            return m_innerList[index];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return m_innerList.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return m_innerList.GetEnumerator();
    }

    public int Count
    {
        get
        {
            return m_innerList.Count;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }

    public static int FindIndexForSortedInsert(List<T> list, Comparer<T> comparer, T item)
    {
        if (list.Count == 0)
        {
            return 0;
        }

        int lowerIndex = 0;
        int upperIndex = list.Count - 1;
        int comparisonResult;
        while (lowerIndex < upperIndex)
        {
            int middleIndex = (lowerIndex + upperIndex) / 2;
            T middle = list[middleIndex];
            comparisonResult = comparer.Compare(middle, item);
            if (comparisonResult == 0)
            {
                return middleIndex;
            }
            else if (comparisonResult > 0) // middle > item
            {
                upperIndex = middleIndex - 1;
            }
            else // middle < item
            {
                lowerIndex = middleIndex + 1;
            }
        }

        // At this point any entry following 'middle' is greater than 'item',
        // and any entry preceding 'middle' is lesser than 'item'.
        // So we either put 'item' before or after 'middle'.
        comparisonResult = comparer.Compare(list[lowerIndex], item);
        if (comparisonResult < 0) // middle < item
        {
            return lowerIndex + 1;
        }
        else
        {
            return lowerIndex;
        }
    }
}

Answer 3

I think the reason is probably just that List<T> already has BinarySearch and Insert, which means implementing your own always-sorted list is trivial.

Not that this means a SortedList<T> class doesn't belong in the framework -- just that it probably wasn't a very high priority since it could easily be written quickly by any developer who needed it.

I think the same was true for HashSet<T>, which didn't originally exist because you could easily use a Dictionary<T, byte> (for example) to simulate one before .NET 3.5.

I know that's what I did in both cases: I had a UniqueSet<T> class and an AlwaysSortedList<T> class, which just wrapped a Dictionary<T, byte> and a List<T> (and used BinarySearch and Insert), respectively.

Answer 4

I think the way to go with this problem is to implement an extension method that adds to List<T> in a sorted manner (just 2 lines of code ;), and then List<T> can be used as a sorted list (assuming you avoid using List.Add(...)):

    public static void AddSorted<T>(this List<T> list, T value)
    {
        int x = list.BinarySearch(value);
        list.Insert((x >= 0) ? x : ~x, value);
    }

Answer 5

It is a list with the sorting being done by the key. I'm just speculating but by providing the ability to specify the key separate from the element, your element doesn't have to be comparable -- only the key need be. I would imagine that in the general case this saves a fair amount of code being developed to implement IComparable since the key is likely a type that is already comparable.

Answer 6

RPM comments is quite valid. Also, with the Linq extensions, you can do sort by any property of T using the Sort extension method. I think that might be the main reasoning behind it.