Can a SortedList<>/SortedDictionary<> with a properly implemented comparer be used to guarantee insertion order?

Question

If the goal is to create a generic read-only dictionary that preserves insertion order, can SortedList<,> or SortedDictionary<,> be realiably used with an IComparer<> that attempts to maintain insertion order by doing something similar to the following?

class OrderedComparer<T> : IComparer<M>
{
    public int Compare(M x, M y)
    {
        return x.Equals(y) ? 0 : -1;//or 1
    }
}
SortedList<M> orderedList = new SortedList<M>(new OrderedComparer<T>());

(It's interesting that in the case of SortedDictionary, the above method need to return 0 or 1 in order to prevent the elements from being sorted in the reverse insertion order).

Answer 1

A comparer must obey the law

Compare(a, b) == -Compare(b, a) //assuming only possible values are -1, 0, 1

This is the symmetry property. Your sample code does not obey it. Therefore the BCL collections do not give you any guarantee at all. You have violated the documented contract.

You can't do this.

Instead, you could add a new field to M where you store the insertion order as an int. You can then use that field in the comparer.

Answer 2

That Compare implementation doesn't follow the rules of symmetry that it should. That's not the right way to go about this.

For a list ordered by insertion order, simply use List<T> as the implementation. With a Dictionary<,>, on the other hand, "The order in which the items are returned is undefined." You could make your own IDictionary<,> implementation that uses these two classes together to do what you're trying to do.

public class MyInsertionOrderDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private List<TKey> keysList;
    private Dictionary<TKey, TValue> dict;

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (TKey key in keysList)
        {
            TValue value = dict[key];
            yield return new KeyValuePair<TKey, TValue>(key, value);
        }
    }

    // TODO implement interface
    // when adding:
    // keysList.Add(key);
    // dict.Add(key, value);

    // when removing:
    // keysList.Remove(key);
    // dict.Remove(key);

    // you could also implement an indexer property like
    public KeyValuePair<TKey, TValue> this[int index] { get { ... } }
}

This class is externally very similar to the OrderedDictionary class, but is generic. There are other generic implementations out there.

Answer 3

There's no question about whether you should do such an horrible thing. You should definitely not, for all kinds of perfectly good reasons, like:

• Don't use sorted containers for unsorted data
• This is not how you use a comparer
• Avoid depending on implementation details of libraries you don't own

Now, to actually know whether you can preserve insertion order in a SortedList by hacking the comparer, there is only one way: look at the implementation. Decompile the bytecode, and see if it would work.

Turns out, SortedList uses a binary search, and SortedDictionary uses a red-black tree.

Fooling the binary search is easy. The comparer is only used for comparing new items (if you don't remove anything). Always return either 1 or -1, I always forget which, and you have an unsorted list.

For the red-black tree, I'm not sure whether the same trick works. I don't remember if that kind of tree has to use the comparer when it rebalances itself. If it does, the inability of your comparer to provide a meaningful result would lead you to runtime errors probably, or at best, loss of complexity guarantees. But maybe it's actually fine. Except that you will still get a maximum amount of rebalancing, I think.