Sorting a Dictionary on a List of Keys

I can almost hear you thinking: "What super-weird problem are you trying to solve!?" Well... it is kind of an abstract one! Imagine you have a dictionary of objects and a separate list of keys in a certain order. Now suppose you want an ordered dictionary based on the list of keys.

According to the documentation the order of the generic Dictionary<TKey, TValue> is not guaranteed. When I tested the order, it looked like it was the same as the insertion order. If you need a sorted dictionary the SortedDictionary<TKey, TValue> is your man.

Building a KeyComparer

So we basically need to influence the sorting-mechanism of the SortedDictionary. This can be done by implementing an IComparer that will do the sorting based on the list of keys. We should adhere to the following rules:

• The position of each key in the list should determine the position in the sorted dictionary.
• If a key has a lower position in the list, the position in the dictionary should be lower as well.
• If a key is not in the list, just put it on the bottom of the dictionary.

Converted into code, it will look like this.

public class KeyComparer<T> : IComparer<T>
{
    private const int TOP = -1;
    private const int BOTTOM = 1;
    private const int EQUAL = 0;

    private readonly Dictionary<T, int> _keys = new Dictionary<T, int>();

    public KeyComparer(IEnumerable<T> keys)
    {
        if (keys != null)
            foreach (var key in keys)
                _keys.Add(key, _keys.Count);
    }

    public virtual int Compare(T x, T y)
    {
        // x is our hero, does he need to be on
        // the top or the bottom of the list?
        int iX = -1, iY = -1;

        if (_keys.TryGetValue(x, out var aX))
            iX = aX;

        if (_keys.TryGetValue(y, out var aY))
            iY = aY;

        // x is not in the list of fields, so
        // x should go to the bottom
        if (iX == -1)
            return BOTTOM;

        // if x and y have the same position,
        // so they must be equal
        if (iX == iY)
            return EQUAL;

        // if y is not in the list, it means
        // x should go to the top. if the position
        // of x in the list is lower, that means
        // x should go to the top.
        if (iY == -1 || iX < iY)
            return TOP;

        // x should go to the bottomn
        return BOTTOM;
    }
}

Implementing the comparer can be quite confusing (it was for me). Fortunately there is documentation. To make things less confusing I used constants instead of integers. Another trick is to make the first parameter the "hero" and think of the compare as deciding if our hero should go to the TOP or BOTTOM of the sorted dictionary.

The result

Now let's compare what happens if we insert a few values in a normal dictionary versus a sorted dictionary (with the new sorter and a list of fields to sort on):

Getting some extensions

I love Linq and it feels like this sorting-feature should be a Linq-like extension as well:

public static class SortingExtensions
{
    public static IDictionary<TKey, TValue> SortBy<TKey, TValue>(
        this IDictionary<TKey, TValue> dictionary, 
        IEnumerable<TKey> keys
    )
    {
        var sorter = new KeyComparer<TKey>(keys);
        return new SortedDictionary<TKey, TValue>(dictionary, sorter);
    }

    public static IDictionary<TKey, TValue> SortByDesc<TKey, TValue>(
        this IDictionary<TKey, TValue> dictionary,
        IEnumerable<TKey> keys
    )
    {
        var sorter = new DescendingKeyComparer<TKey>(keys);
        return new SortedDictionary<TKey, TValue>(dictionary, sorter);
    }
}

public class DescendingKeyComparer<T> : KeyComparer<T>
{
    public DescendingKeyComparer(IEnumerable<T> keys) : base(keys)
    {
    }

    public override int Compare(T x, T y)
    {
        return base.Compare(x, y) * -1;
    }
}

So that's it, we can sort. The world has order again.