是否有一个Queue(PriorityQueue)实现也是一个Set？

Question

我正在寻找一个也是一个Set的PriorityQueue实现.

的compareTo,如果它的元素一定不能有要求实施与执行相一致equals.

有没有这样的java实现？

更新:我现在使用SortedSet作为内部集合来实现它.所以我只需要实现缺少的方法来满足队列接口.我也忘了提到它也必须是一个有界的队列,因此它具有容量并在达到容量时丢弃该组的最后一个元素.

Answer 1

如果有一个具有"类似Set"行为的队列就足够了,那么你只是不想接受重复的条目,那么我认为,一个简单的解决方案可能是子类化PriorityQueue和覆盖add(),addAll()以及offer()类似的方法:

@Override
public boolean offer(E e) {
  if (contains(e)) {
    return false; 
  } else {
    return super.offer(e);
  }
}

BTW - 在内部add()调用offer(),所以也许甚至可以覆盖offer()方法并在那里进行检查.

Answer 2

那么，它PriorityQueue本身将取决于Comparitor项目的排序或自然顺序，同样，它也Set将取决于自然顺序或Comparitor功能，所以不，我不认为它作为默认 Java 安装的一部分存在。 ..

但是，如果不担心速度的话，您可以很容易地创建一个，只需实现您想要的接口，并使用它们的自然支持等......又名

MyQueueSet extends PriorityQueue implements Set {
    HashSet set;
    ...
}

不幸的是，Java 的 java.util.* 数据集类并不总是最容易在不重写其代码块的情况下扩展的。

支持PriorityQueue是堆排序的元素列表，因此插入一个新元素然后进行测试contains(e)将进行 O(n) 搜索，因为排序是基于队列，而不是数据值，如果您包括HashSet支持该Set功能的话，您可以大大缩短查找时间，但代价是两次维护数据集引用（请记住，Java 是按值传递的，所有对象都位于堆上）。这应该可以提高大型集合的性能。