.net - 为什么 .Net 框架没有优先级队列类？

Question

Stack Overflow 上有一些线程处理在 .Net 和 C# 中实现优先级队列。

我的问题具有更基本的性质：为什么 .Net 框架中没有开箱即用的优先级队列？甚至 C++ 标准库也有一个。

Answer 1

前段时间有一个问题（为什么 C# 确实允许像 C++ 这样的非成员函数），这促使 Eric Lippert 写了一篇关于原因的博客文章。在其中，他解释说：

我被问到“为什么 C# 不实现功能 X？” 每时每刻。答案总是一样的：因为从来没有人设计、指定、实施、测试、记录和发布该功能。所有这六件事都是使功能发生所必需的。所有这些都花费了大量的时间、精力和金钱。功能并不便宜，鉴于我们有限的时间、精力和金钱预算，我们非常努力地确保我们只发布那些为我们的用户带来最大利益的功能。

我怀疑这可能就是为什么.Net 没有提供优先级队列的答案——只是没有足够的时间、精力、金钱、需求（？）来实现一个。

Answer 2

.NET 4.0 引入了一个SortedSet<T>类，以及ISet<T>由SortedSet<T>和实现的接口HashSet<T>。这显然会使实现您自己的PriorityQueue<T>类变得更简单。

但是，仍然没有IQueue<T>接口，至少承认需要优先级队列或除基本 BCL 之外的任何其他实现Queue<T>。同样，没有IStack<T>.

就我个人而言，我发现缺少这些最基本的接口令人失望和短视，特别是因为从现有类中提取简单接口的设计/规范/实现/测试/文档成本确实应该非常低。

public interface IQueue<T> : IEnumerable<T>, ICollection, IEnumerable
{
    T Dequeue();
    void Enqueue(T item);
    T Peek();
}

在那里，看到了吗？我已经做到了。

Answer 3

这已正式宣布并在 .NET 6 预览版中。

PriorityQueue<TElement, TPriority> (System.Collections.Generic) 是一个新集合，可以添加具有值和优先级的新项目。在出队时，PriorityQueue 返回具有最低优先级值的元素。您可以认为这个新集合类似于 Queue，但每个入队元素都有一个影响出队行为的优先级值。

以下示例演示了 PriorityQueue<string, int> 的行为。

// creates a priority queue of strings with integer priorities
var pq = new PriorityQueue<string, int>();

// enqueue elements with associated priorities
pq.Enqueue("A", 3);
pq.Enqueue("B", 1);
pq.Enqueue("C", 2);
pq.Enqueue("D", 3);

pq.Dequeue(); // returns "B"
pq.Dequeue(); // returns "C"
pq.Dequeue(); // either "A" or "D", stability is not guaranteed.

Answer 4

截至 2021 年 1 月，.Net Core 添加了 PriorityQueue 实现。可以在此处找到对 repo 和 API 的实际提交：https ://github.com/dotnet/runtime/commit/826aa4f7844fd3d48784025ec6d47010867baab4

Answer 5

它现在作为 .NET6 的一部分提供。查看以下博客文章以了解实施情况。

https://dotnetcoretutorials.com/2021/03/17/priorityqueue-in-net/

Answer 6

看到这个：将 PriorityQueue 添加到 Collections，他们需要5 年，仍然没有 PriorityQueue 。