Click here to Skip to main content
12,446,146 members (27,261 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

18.2K views
100 downloads
13 bookmarked
Posted

SortableDictionary

, 4 Apr 2009 CPOL
Rate this:
Please Sign up or sign in to vote.
An extension to the existing .NET Dictionary that allows sorting by key and by value
SortableDictionary_src_and_demo

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. 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

dybs
United States United States
No Biography provided

You may also be interested in...

Pro
Pro

Comments and Discussions

 
GeneralUsing sorted heaps Pin
darrellp4-Apr-09 16:56
memberdarrellp4-Apr-09 16:56 
GeneralRe: Using sorted heaps Pin
dybs4-Apr-09 17:14
memberdybs4-Apr-09 17:14 
GeneralRe: Using sorted heaps Pin
darrellp4-Apr-09 20:32
memberdarrellp4-Apr-09 20:32 
GeneralThoughts Pin
PIEBALDconsult4-Apr-09 16:15
memberPIEBALDconsult4-Apr-09 16:15 
GeneralRe: Thoughts Pin
dybs4-Apr-09 16:48
memberdybs4-Apr-09 16:48 
GeneralRe: Thoughts Pin
PIEBALDconsult4-Apr-09 19:19
memberPIEBALDconsult4-Apr-09 19:19 
GeneralExisting sorteddictionary class Pin
MAHESHSETHI4-Apr-09 14:59
memberMAHESHSETHI4-Apr-09 14:59 
GeneralRe: Existing sorteddictionary class Pin
dybs4-Apr-09 15:57
memberdybs4-Apr-09 15:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.160811.3 | Last Updated 4 Apr 2009
Article Copyright 2009 by dybs
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid