c# - 获取 SortedDictionary 中的最后一个元素

Question

我看到 this question .

如何在 .Net 3.5 中获取 SortedDictionary 中的最后一个元素。

Answer 1

Last扩展方法会给你结果，但它必须枚举整个集合才能到达那里。太可惜了SortedDictionary<K, V>不公开 Min和 Max成员特别是在内部考虑它得到了 SortedSet<KeyValuePair<K, V>> 的支持其中有 Min和 Max特性。

如果 O(n) 不是理想的，您有几个选择:

1. 切换到 SortedList<K, V> .同样出于某种原因，BCL 默认不打包它。您可以使用索引器在 O(1) 时间内获取最大(或最小)值。使用扩展方法进行扩展会很好。

   //Ensure you dont call Min Linq extension method.
   public KeyValuePair<K, V> Min<K, V>(this SortedList<K, V> dict)
   {
       return new KeyValuePair<K, V>(dict.Keys[0], dict.Values[0]); //is O(1)
   }
   
   //Ensure you dont call Max Linq extension method.
   public KeyValuePair<K, V> Max<K, V>(this SortedList<K, V> dict)
   {
       var index = dict.Count - 1; //O(1) again
       return new KeyValuePair<K, V>(dict.Keys[index], dict.Values[index]);
   }
   

   SortedList<K, V>伴随着其他处罚。所以你可能想看看:What's the difference between SortedList and SortedDictionary?

2. 自己写SortedDictionary<K, V>类(class)。这是非常微不足道的。有SortedSet<KeyValuePair<K, V>>作为内部容器并根据 Key 进行比较部分。像这样的东西:

   public class SortedDictionary<K, V> : IDictionary<K, V>
   {
       SortedSet<KeyValuePair<K, V>> set; //initialize with appropriate comparer
   
       public KeyValuePair<K, V> Min { get { return set.Min; } } //O(log n)
       public KeyValuePair<K, V> Max { get { return set.Max; } } //O(log n)
   }
   

   这是 O(log n)。没有记录，但我检查了代码。

3. 使用精细的反射访问作为 SortedDictionary<K, V> 私有(private)成员的支持集类并调用 Min和 Max特性。可以依靠表达式来编译委托(delegate)并将其缓存以提高性能。这样做是一个非常糟糕的选择。不敢相信我提出了这个建议。

4. 依赖于其他实现，例如。对于 TreeDictionary<K, V> from C5 .他们有 FindMin 和 FindMax both of which are O(log n)