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.
public void SortByKey(bool ascending)
{
TKey[] keys = new TKey[Count];
TValue[] vals = new TValue[Count];
Keys.CopyTo(keys, 0);
Values.CopyTo(vals, 0);
Array.Sort<TKey, TValue>(keys, vals);
if(!ascending)
{
Array.Reverse(keys);
Array.Reverse(vals);
}
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. 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 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
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.