.NET中的反向排序字典

Question

有没有办法在C#中反向迭代（倒序）SortedDictionary？

或者有没有一种方法可以预定义降序的 SortedDictionary？

- Gal Goldman

---

错别字...感谢所有的人类编译器 :-) - Gal Goldman

Answer 1

SortedDictionary本身不支持反向迭代，但您有几种可能实现相同的效果。

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.

编辑 :: 对SortedLists的迭代

您可以通过索引访问元素！

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

- Dario

---

这个库在IComparer<T>上定义了一个Reverse()扩展方法，使比较器的使用更加简洁。点击此处查看详情。 - ChaseMedallion

Answer 2

定义 SortedDictionary 以相反的顺序开始的最简单方法是提供一个 IComparer<TKey>，该比较器按照与正常顺序相反的顺序进行排序。

这里是来自 MiscUtil 的一些代码，可能会让您更容易实现：

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

然后你会使用：

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

（或者你使用的任何类型）。

如果您只想单向迭代，那么这比之后反转顺序更有效率。

- Jon Skeet

---

提供从Comparison<T>到Comparer<T>的框架集成转换方法将非常有用，因为委托更容易处理（lambda方法）;-) - Dario

我也有一个在MiscUtil中的类可以做到这一点 :) - Jon Skeet

很好；-）应该成为框架的一部分。甚至内部有这样一个类，但它是私有的；-） - Dario

@Dario 绝对没错。这个框架中的“遗漏”在2012年（.NET 4.5）得到了纠正，当时引入了method Comparer<>.Create，它接受一个Comparison<>委托并返回相应的IComparer<>（实际上它返回一个同时实现了IComparer<>和IComparer的Comparer<>）。 - Jeppe Stig Nielsen

Answer 3

用一行代码简要创建一个反向排序的字典。

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

使用 System.Collections.Generic.Comparer<T> 可以创建一个 IComparer<T>。只需将 IComparison<T> 委托传递给其 Create 方法即可构建一个 IComparer<T>。

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

你可以使用 lambda表达式/本地函数/方法 来替换委托，如果它们的重要性是 (TKey, TKey) => int。

- Zheng Chen

Answer 4

如果你使用数字值作为键，也有一个非常简单的方法，那就是在创建字典时将它们取反。

- jpope

---

这实际上是一个非常好的方法。 - dicemaster

Answer 5

如果您正在使用.NET 3.5，您可以使用OrderByDescending扩展方法：

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

- BFree

---

太糟糕了！OrderByDescending需要O(nlogn)的时间来对已经排序过的数据进行排序！ - Dario