1

我在 C# 中有一个优先级队列实现，我想添加一个 .IndexOf 方法。

但是，由于优先级队列并不真正关心值本身的顺序（也就是说，如果我只是抓取所有值，而忽略它们的优先级，它们根本就不一定有任何顺序），只有它们的优先级，我对优先级队列的泛型 T 没有任何标准，也就是说，我没有指定它们需要具有某种内在顺序或可比性。

因此，当我开始实施时，我遇到了.IndexOf(T value)一个小问题。

有什么/我应该如何实施的标准吗？我最初的想法只是用来EqualityComparer<T>.Default判断我是否找到了value，但是现在有很多类似的类型。

例如，这是我想出的覆盖我的基础的东西，但这似乎有点过分了：

  • public Int32 IndexOf(T value)（内部调用其他之一ClassThatImplementsInterface.Default）
  • public Int32 IndexOf(T value, IComparer<T> comparer)
  • public Int32 IndexOf(T value, IEqualityComparer<T> comparer)
  • public Int32 IndexOf(T value, IEquatable<T> comparer)
  • public Int32 IndexOf(T value, Predicate<T> predicate)

你做什么工作？将其标记为主观和维基，因为这更像是民意调查而不是其他任何事情。

在重新阅读我自己的问题时，我想我可以只使用没有比较器的问题，然后添加谓词版本，这样这个类的用户几乎可以调用任何东西。

另请注意，我也可以pq[index]获取同时包含优先级和值本身的项目，因此我也可以完全不使用 IndexOf，但我也希望有方法可以更改值的优先级X 优先级 P，这将需要某种形式的 IndexOf/search 内部。因此，我还想避免所有这些方法的无数次重载。

对评论的回应：是的，优先级队列是基于堆的。

基本上，这两个类是这样定义的：

public class Heap<T> : IEnumerable<T>, ICloneable { ... }
public class PriorityQueue<T> : Heap<PriorityQueueElement<T>> { ... }

PriorityQueueElement 是一个简单的不可变结构，具有 Priority 和 Value 属性。

Response to forthcoming comment: Since the priority queue is based on a heap, an "interesting property" is that by changing the priority of a value through its index means that afterwards, the value won't necessarily be at that index. I intend to just document this as in some cases I foresee a need for independent locate/change-priority operations.

4

1 回答 1

2

I would make the comparison an optional constructor parameter; this is comparable to how things like Dictionary<,>, SortedList<,> etc allow you to specify the comparison mechanism.

是否接受 anIComparer<T>或 anIEqualityComparer<T>取决于您是要对数据进行排序，还是只寻找相等匹配；如果匹配，那么您将需要类似IEqualityComparer<T>. 不幸的是，由于 this 有 2 个方法 (GetHashCode()和Equals())，因此没有直接的委托版本，除了Predicate<T>or Func<T,T,bool>。

对于默认构造函数，我会传入[Equality]Comparer<T>.Default.

于 2008-12-29T10:08:47.480 回答