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.