Reverse Sorted Dictionary in .NET

Is there any way I can iterate backwards (in reverse) through a SortedDictionary in c#?

Or is there a way to define the SortedDictionary in descending order to begin with?

The SortedDictionary itself doesn't support backward iteration, but you have several possibilities to achieve the same effect.

1. Use .Reverse-Method (Linq). (This will have to pre-compute the whole dictionary output but is the simplest solution)

   var Rand = new Random();
   
   var Dict = new SortedDictionary<int, string>();
   
   for (int i = 1; i <= 10; ++i) {
       var newItem = Rand.Next(1, 100);
       Dict.Add(newItem, (newItem * newItem).ToString());
   }
   
   foreach (var x in Dict.Reverse()) {
       Console.WriteLine("{0} -> {1}", x.Key, x.Value);
   }
   

2. Make the dictionary sort in descending order.

   class DescendingComparer<T> : IComparer<T> where T : IComparable<T> {
       public int Compare(T x, T y) {
           return y.CompareTo(x);
       }
   }
   
   // ...
   
   var Dict = new SortedDictionary<int, string>(new DescendingComparer<int>());
   

3. Use SortedList<TKey, TValue> instead. The performance is not as good as the dictionary's (O(n) instead of O(logn)), but you have random-access at the elements like in arrays. When you use the generic IDictionary-Interface, you won't have to change the rest of your code.

Edit :: Iterating on SortedLists

You just access the elements by index!

var Rand = new Random();


var Dict = new SortedList<int, string>();

for (int i = 1; i <= 10; ++i) {
    var newItem = Rand.Next(1, 100);
    Dict.Add(newItem, (newItem * newItem).ToString());
}

// Reverse for loop (forr + tab)
for (int i = Dict.Count - 1; i >= 0; --i) {
    Console.WriteLine("{0} -> {1}", Dict.Keys[i], Dict.Values[i]);
}

The easiest way to define the SortedDictionary in the reverse order to start with is to provide it with an IComparer<TKey> which sorts in the reverse order to normal.

Here's some code from MiscUtil which might make that easier for you:

using System.Collections.Generic;

namespace MiscUtil.Collections
{
    /// <summary>
    /// Implementation of IComparer{T} based on another one;
    /// this simply reverses the original comparison.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public sealed class ReverseComparer<T> : IComparer<T>
    {
        readonly IComparer<T> originalComparer;

        /// <summary>
        /// Returns the original comparer; this can be useful
        /// to avoid multiple reversals.
        /// </summary>
        public IComparer<T> OriginalComparer
        {
            get { return originalComparer; }
        }

        /// <summary>
        /// Creates a new reversing comparer.
        /// </summary>
        /// <param name="original">The original comparer to 
        /// use for comparisons.</param>
        public ReverseComparer(IComparer<T> original)
        {
            if (original == null)
            { 
                throw new ArgumentNullException("original");
            }
            this.originalComparer = original;
        }

        /// <summary>
        /// Returns the result of comparing the specified
        /// values using the original
        /// comparer, but reversing the order of comparison.
        /// </summary>
        public int Compare(T x, T y)
        {
            return originalComparer.Compare(y, x);
        }
    }
}

You'd then use:

var dict = new SortedDictionary<string, int>
     (new ReverseComparer<string>(StringComparer.InvariantCulture));

(or whatever type you were using).

If you only ever want to iterate in one direction, this will be more efficient than reversing the ordering afterwards.

Briefly create a reversed sorted dictionary in one line.

var dict = new SortedDictionary<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));

There's a way to create a IComparer<T> using System.Collections.Generic.Comparer<T>. Just pass a IComparision<T> delegate to its Create method to build a IComparer<T>.

var dict = new SortedDictionary<int, TValue>(
    Comparer<int>.Create(
        delegate(int x, int y)
        {
            return y.CompareTo(x);
        }
    )
);

You can use a lambda expression/local function/method to replace the delegate if their significance are (TKey, TKey) => int.

There is also a very simple approach if you are dealing with numeric values as the key which is to simply negate them when you create the dictionary.

If you're using .NET 3.5, you can use the OrderByDescending extension method:

        var dictionary = new SortedDictionary<int, string>();
        dictionary.Add(1, "One");
        dictionary.Add(3, "Three");
        dictionary.Add(2, "Two");
        dictionary.Add(4, "Four");

        

        var q = dictionary.OrderByDescending(kvp => kvp.Key);
        foreach (var item in q)
        {
            Console.WriteLine(item.Key + " , " + item.Value);
        }