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

发布于 2024-08-14 20:00:40 字数 122 浏览 12 评论 0原文

Stack Overflow 上有一些线程涉及在 . NET 和 C#。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梓梦 2024-08-21 20:00:40

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

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

我怀疑这可能就是 .Net 不附带优先级队列的原因 - 只是没有足够的时间、精力、金钱、需求（？）来实现优先级队列。

回复收藏 0 原文

傾旎 2024-08-21 20:00:40

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

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

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

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

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

.NET 4.0 introduces a SortedSet<T> class, along with the ISet<T> interface which is implemented by SortedSet<T> and HashSet<T>. This will obviously make it simpler to implement your own PriorityQueue<T> class.

However, there is still no IQueue<T> interface, which would at least admit the need for priority queues or any other implementation than the basic BCL Queue<T>. Similarly, there's no IStack<T>.

Personally I find this lack of some of these most basic interfaces disappointing and short-sighted, especially as the design/specification/implementation/testing/documentation cost of extracting a simple interface from an existing class should be very low indeed.

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

There, see? I've done it.

回复收藏 0 原文

断舍离 2024-08-21 20:00:40

这已正式宣布，并且位于 . NET 6 预览。

PriorityQueue(System.Collections.Generic) 是一个新集合，可以添加具有值和优先级的新项目。在出队时，PriorityQueue 返回具有最低优先级值的元素。您可以将这个新集合视为与 Queue 类似，但每个入队元素都有一个优先级值，该值会影响出队行为。
以下示例演示了 PriorityQueue的行为。
// 创建具有整数优先级的字符串优先级队列
var pq = new PriorityQueue();

// 将具有关联优先级的元素放入队列
pq.Enqueue("A", 3);
pq.Enqueue("B", 1);
pq.Enqueue("C", 2);
pq.Enqueue("D", 3);

pq.Dequeue(); // 返回“B”
pq.Dequeue(); // 返回“C”
pq.Dequeue(); // 无论是“A”还是“D”，都不保证稳定性。

This has been officially announced and is in the .NET 6 preview.

PriorityQueue<TElement, TPriority> (System.Collections.Generic) is a new collection that enables adding new items with a value and a priority. On dequeue the PriorityQueue returns the element with the lowest priority value. You can think of this new collection as similar to Queue but that each enqueued element has a priority value that affects the behavior of dequeue.
The following sample demonstrates the behavior of 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.

回复收藏 0 原文

涫野音 2024-08-21 20:00:40

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

回复收藏 0 原文