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.
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.
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 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.
public void SortByKey(bool ascending)
TKey keys = new TKey[Count];
TValue vals = new TValue[Count];
Array.Sort<TKey, TValue>(keys, vals);
for (int i = 0; i < keys.Length; i++)
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. 3rd 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
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:
You can use the
SortableDictionary just like you would an ordinary
Dictionary, with the addition of the
SortByValue methods. Each method has two overloads.
SortByKey/Value() sorts in ascending order by default.
SortByKey/Value(bool) lets you specify the order.
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.
April 4, 2009
- Initial version
- Added comparison with existing
SortedDictionary in .NET Framework