获取 SortedDictionary 中的最后一个元素

Question

我看到了这个问题。

在.NET 3.5中，如何获取排序字典(SortedDictionary)中的最后一个元素？

- leora

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>有一些其他的惩罚。因此，您可能想查看：SortedList和SortedDictionary之间的区别是什么？

编写自己的 SortedDictionary<K，V>类。这非常简单。使用Key部分作为比较基础，将SortedSet<KeyValuePair<K，V>>作为内部容器。类似于下面的代码：

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)。虽然没有记录，但我检查了代码。

使用繁琐的反射访问SortedDictionary<K, V>类的私有成员来访问后备集，并调用Min和Max属性。可以依靠表达式来编译委托并对其进行缓存以提高性能。这是一个非常糟糕的选择。不敢相信我会建议这样做。

依赖其他实现，例如C5中的TreeDictionary<K,V>。它们都有FindMin和FindMax，两者的时间复杂度均为O(log n)。

- nawfal

---

可能需要重新排列这些选项，以便更好的选项排在前面，而不是按照您认为的顺序排列。 - Servy

你会如何为第二个选项实现索引器/TryGetValue？ - CodesInChaos

@CodesInChaos 你是对的，那样做就没用了。在.NET中，集合不提供获取实际引用的方法，这很遗憾。我应该编辑答案。 - nawfal

这仍然是GitHub上的一个未解决问题：SortedDictionary.First performance。似乎由于某种原因，他们不喜欢向现有的集合类型添加新功能。 - Theodor Zoulias

Answer 2

你可以使用 LINQ：

var lastItem = sortedDict.Values.Last();

你也可以获取最后一个键：

var lastkey = sortedDict.Keys.Last();

你甚至可以获取最后一个键值对：

var lastKeyValuePair = sortedDict.Last();

这将为您提供一个带有Key和Value属性的KeyValuePair<TKey, TValue>。

请注意，如果字典为空，这将会引发异常。如果不想这样，请调用LastOrDefault。

- SLaks

---

这些方法可能会触发枚举。我想知道是否有任何方法可以在不进行枚举的情况下获取最后一个元素（或任意位置索引的元素）？由于SortedDictionary是排序为树形结构的，理论上可能是可行的。 - Roland Pihlakas

@RolandPihlakas：理论上是可以的。但实际上，我认为不行。 - SLaks

对于一个C++背景的人来说，这很难接受。枚举整个排序字典只为了获取最后一个元素是非常低效的。是否有更强大的C#集合库可用？ - avl_sweden

@ThunderGr：没有，它没有索引器。 - SLaks

@Lander：一旦您移除一个元素，那将完全破坏。 - SLaks

Answer 3

你可以使用 SortedDictionary.Values.Last(); 来获取最后一个值。

如果你想要键和值，可以使用：

SortedDictionary.Last();

- kemiller2002

Answer 4

SortedList列表...

list[ Keys[Keys.Count - 1] ];  // returns the last entry in list

- DakotaTimber

Answer 5

正如其他人所指出的那样，Last扩展将枚举整个集合，对性能的影响可能是致命的。仅仅是从SortedDict中删除最后10000个元素，所花费的时间比在SortedSet上执行类似操作要多得多。

SortedSet移除所用时间：8毫秒 SortedDict移除所用时间：3697毫秒 // 在下面的代码中，ss是SortedSet，sd是SortedDictionary，它们都包含相同的10000个元素。 sw.Start(); while (ss.Count != 0) { ss.Remove(ss.Max); }

sw.Stop(); Console.WriteLine("SortedSet移除所用时间：{0}", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start(); while (sd.Count != 0) { sd.Remove(sd.Keys.Last()); }

sw.Stop(); Console.WriteLine("字典移除所用时间：{0}", sw.ElapsedMilliseconds);

- Ujjwal Uttaray