Is there a SortedList<T> class in .NET?

Question

I need to sort some objects according to their contents (in fact according to one of their properties, which is NOT the key and may be duplicated between different objects).

.NET provides two classes (SortedDictionary and SortedList), and both are implemented using a binary tree. The only differences between them are

• SortedList uses less memory than SortedDictionary.
• SortedDictionary has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList.
• If the list is populated all at once from sorted data, SortedList is faster than SortedDictionary.

I could achieve what I want using a List, and then using its Sort() method with a custom implementation of IComparer, but it would not be time-efficient as I would sort the whole List each time I want to insert a new object, whereas a good SortedList would just insert the item at the right position.

What I need is a SortedList class with a RefreshPosition(int index) to move only the changed (or inserted) object rather than resorting the whole list each time an object inside changes.

Am I missing something obvious ?

Answer 1

Maybe I'm slow, but isn't this the easiest implementation ever?

class SortedList<T> : List<T>
{
    public new void Add(T item)
    {
        Insert(~BinarySearch(item), item);
    }
}

http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

---

Unfortunately, Add wasn't overrideable so I had to new it which isn't so nice when you have List<T> list = new SortedList<T>; which I actually needed to do.... so I went ahead and rebuilt the whole thing...

class SortedList<T> : IList<T>
{
    private List<T> list = new List<T>();

    public int IndexOf(T item)
    {
        var index = list.BinarySearch(item);
        return index < 0 ? -1 : index;
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException("Cannot insert at index; must preserve order.");
    }

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

    public T this[int index]
    {
        get
        {
            return list[index];
        }
        set
        {
            list.RemoveAt(index);
            this.Add(value);
        }
    }

    public void Add(T item)
    {
        list.Insert(~list.BinarySearch(item), item);
    }

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

    public bool Contains(T item)
    {
        return list.BinarySearch(item) >= 0;
    }

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

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

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(T item)
    {
        var index = list.BinarySearch(item);
        if (index < 0) return false;
        list.RemoveAt(index);
        return true;
    }

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

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

---

Or perhaps something like this is a more appropriate Remove function...

    public bool Remove(T item)
    {
        var index = list.BinarySearch(item);
        if (index < 0) return false;
        while (((IComparable)item).CompareTo((IComparable)list[index]) == 0)
        {
            if (item == list[index])
            {
                list.RemoveAt(index);
                return true;
            }
            index++;
        }
        return false;
    }

Assuming items can compare equal but not be equal...

Answer 2

I eventually decided to write it :

class RealSortedList<T> : List<T>
    {
        public IComparer<T> comparer;

        public int SortItem(int index)
        {
            T item = this[index];
            this.RemoveAt(index);
            int goodposition=FindLocation(this[index], 0, this.Count);
            this.Insert(goodposition, item);
            return goodposition;
        }

        public int FindLocation(T item, int begin, int end)
        {
            if (begin==end)
                return begin;
            int middle = begin + end / 2;
            int comparisonvalue = comparer.Compare(item, this[middle]);
            if (comparisonvalue < 0)
                return FindLocation(item,begin, middle);
            else if (comparisonvalue > 0)
                return FindLocation(item,middle, end);
            else
                return middle;
        }
    }

Answer 3

Don't forget that inserting an item into a list backed by an array can be an expensive operation - inserting a bunch of items and then sorting may well be quicker unless you really need to sort after every single operation.

Alternatively, you could always wrap a list and make your add operation find the right place and insert it there.

Answer 4

I've solved this problem in the past by writing an extension method that does a binary search on a IList, and another that does an insert. You can look up the correct implementation in the CLR source because there's a built-in version that works only on arrays, and then just tweak it to be an extension on IList.

One of those "should be in the BCL already" things.

Answer 5

What I need is a SortedList class with a RefreshPosition(int index) to move only the changed (or inserted) object rather than resorting the whole list each time an object inside changes.

Why would you update using an index when such updates invalidate the index? Really, I would think that updating by object reference would be more convenient. You can do this with the SortedList - just remember that your Key type is the same as the return type of the function that extracts the comparable data form the object.

class UpdateableSortedList<K,V> {
    private SortedList<K,V> list = new SortedList<K,V>();
    public delegate K ExtractKeyFunc(V v);
    private ExtractKeyFunc func;

    public UpdateableSortedList(ExtractKeyFunc f) { func = f; }

    public void Add(V v) {
        list[func(v)] = v;
    }
    public void Update(V v) {
        int i = list.IndexOfValue(v);
        if (i >= 0) {
            list.RemoveAt(i);
        }
        list[func(v)] = v;
    }
    public IEnumerable<T> Values { get { return list.Values; } }
}

Something like that I guess.