Reverse Sorted Dictionary in .NET

Question

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?

Answer 1

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]); } 

Answer 2

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.