10

SetでもあるPriorityQueue実装を探しています。

要素の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）検索が行われます。 、データセット参照を2回維持することを犠牲にして、ルックアップ時間を大幅に改善できます（Javaは値渡しであり、すべてのオブジェクトはヒープ上に存在することに注意してください）。これにより、大規模なセットのパフォーマンスが向上するはずです。HashSetSet

于 2009-12-08T19:02:39.663 に答える
0

PriorityQueue は AbstractCollection です。これは Set とほぼ同じインターフェイスを持っています。PriorityQueue を Set に変換するラッパーを作成するのは簡単だと思います。本当にそれを強制する必要がある場合は、挿入された要素のサイドハッシュテーブルを保持して、重複を避けることができます。

PriorityQueue では、compareTo が equals と一致している必要はないと思います。PriorityQueue は equals をまったく使用しません (継承された AbstractCollection 操作を除いて?)。

于 2009-12-08T19:07:31.907 に答える