10

我正在寻找一个PriorityQueue实现，它也是一个Set。

如果其元素的compareTo实现必须不要求与equals.

java有没有这样的实现？

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

4

4 回答 4

7

如果有一个具有“类似集合”行为的队列就足够了，那么您只是不想接受重复的条目，那么我认为，一个简单的解决方案可能是子类PriorityQueue化并覆盖add(),addAll()和offer()方法，例如：

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

顺便说一句 -在内部add()调用offer()，所以也许只覆盖该offer()方法并在那里进行检查就足够了。

于 2009-12-08T19:04:38.637 回答
3

TreeSet是一个提供有序迭代器的集合。它实现了SortedSet接口，该接口保证该iterator方法返回的迭代器将按升序返回集合的元素，这由它们的自然顺序（通过Comparable）确定，或者由在创建集合时给定的比较器确定。

于 2011-08-08T03:06:51.713 回答
1

好吧，PriorityQueue它本身将取决于Comparitor项目的排序或自然排序，同样，Set这将取决于自然排序或Comparitor函数，所以不，我不认为作为默认 Java 安装的一部分存在。 ..

但是，如果您不担心速度，您可以轻松地创建一个，只需实现您想要的接口，并使用它们的自然支持等……也就是

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

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

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

于 2009-12-08T19:02:39.663 回答
0

PriorityQueue 是一个 AbstractCollection - 它具有与 Set 几乎相同的接口。我确信制作一个将 PriorityQueue 转换为 Set 的包装器会很容易。如果您确实需要强制执行，您可以保留插入元素的侧面哈希表以避免重复。

我不认为 PriorityQueue 要求 compareTo 与 equals 一致。PriorityQueue 根本不使用 equals（除了它继承的 AbstractCollection 操作？）。

于 2009-12-08T19:07:31.907 回答