SortableDictionary

• Download source and demo - 24.28 KB

Introduction

This article provides an extension to the existing .NET Dictionary that can be sorted by key or by value, in ascending or descending order. By the way, this is my first article, so any feedback is appreciated.

Background

In several recent projects, I've needed to organize data in a Dictionary structure, but I've also needed that data sorted in different orders. Other implementations sort by key only, or by value only (A Dictionary Collection Sorting By Value), and implement a lot of things from scratch. This is an attempt at a much simpler implementation, using functionality already part of the .NET Framework.

One reader commented on the existing SortedDictionary class in the .NET Framework. This collection constantly maintains its sorted order, and is only sorted by key. Also, it is always in ascending order (unless you specify a different IComparer that sorts the other way). The SortableDictionary presented here allows sorting by key or by value, in either direction, although new items are still inserted at the end. If new items are added to the SortableDictionary after sorting it, it must be resorted.

The Code

The SortableDictionary class inherits from the System.Collections.Generic.Dictionary class, with the constraint that the key and value types implement the IComparable interface. This is required for using the built-in Array.Sort function. See the class declaration below:

public class SortableDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    where TKey : Comparable<TKey>
    where TValue : IComparable<TValue> 

The meat of this class is in SortByKey and SortByValue. SortByKey is shown below. NOTE: This function relies on the fact that the keys and values are retrieved from a dictionary in the same order they were inserted.

/// <summary>
/// Sorts the dictionary according to key.
/// Allows specifying the sort order.
/// </summary>
/// <param name="ascending">True to sort in ascending order.
/// False to sort in descending order.</param>
public void SortByKey(bool ascending)
{
    // Get the keys and values as arrays.
    // They will be in the same order as they are in the
    // dictionary.                
    TKey[] keys = new TKey[Count];
    TValue[] vals = new TValue[Count];
    Keys.CopyTo(keys, 0);
    Values.CopyTo(vals, 0);

    // Use the built-in array sort function.
    // This particular overload sorts reorders both they
    // "keys" and "vals" arrays in matching order, but the
    // array used to determine the order is "keys".
    Array.Sort<TKey, TValue>(keys, vals);

    // The default sort order is ascending.
    // If ascending is false, simply reverse the arrays.
    if(!ascending)
    {
        Array.Reverse(keys);
        Array.Reverse(vals);
    }

    // Clear out the dictionary and re-add the key-value pairs
    // in the new order.
    Clear();
    for (int i = 0; i < keys.Length; i++)
    {
         Add(keys[i], vals[i]);
    }
}

The parameter ascending indicates the order the dictionary should be sorted in.

First I copy the keys and values into separate arrays. Then I sort them together using Array.Sort(). I discovered this particular overload by accident (MSDN documentation was quite helpful here. 3^rd entry on this page). If you're not familiar with this overload, the first argument (keys) is the array that is actually sorted. The second argument (vals) is another array of the same length, that is reordered in parallel with the keys array. This is precisely the effect I wanted with SortableDictionary, so I decided not to reinvent the wheel.

The default order for Array.Sort() is ascending. If SortByKey/Value is called with a parameter of false (descending order), then the key and value arrays are reversed after the sort.

After the sort is complete, the dictionary is cleared, and the key-value pairs are re-added to the dictionary in the new order. And we're done!

The only difference between SortByKey and SortByValue is the line:

Array.Sort<TKey, TValue>(keys, vals)

SortByValue uses the vals array as the sort key, so this line changes to:

Array.Sort<TValue, TKey>(vals, keys) 

Using the Code

To use this class, simply add SortableDictionary.dll as a reference to your project, and add the following line to your source file:

using Dybs.Controls;

You can use the SortableDictionary just like you would an ordinary Dictionary, with the addition of the SortByKey and SortByValue methods. Each method has two overloads. SortByKey/Value() sorts in ascending order by default. SortByKey/Value(bool) lets you specify the order.

Conclusion

That's all there is to it! I'm sure there are more efficient methods, but this should work for most cases. Thanks for reading and I look forward to your comments! Any suggestions are greatly appreciated.

History

April 4, 2009

• Initial version
• Added comparison with existing SortedDictionary in .NET Framework