Ich bin auf der Suche nach einer PriorityQueue Implementierung ist auch ein Set .
Die compareTo Implementierung, wenn ihre Elemente nicht konsistent mit der Implementierung von equals sein müssen.
Gibt es irgendwo eine solche Implementierung für Java?
Update: Ich habe es jetzt mit einem SortedSet als interne Sammlung implementiert. Also musste ich nur die fehlenden Methoden implementieren, um die Warteschlangenschnittstelle zu erfüllen. Ich habe auch vergessen zu erwähnen, dass es auch eine beschränkte Warteschlange sein musste, so dass es eine Kapazität aufweist und das letzte Element des Satzes verwirft, wenn die Kapazität erreicht ist.
Wenn es ausreichend ist, eine Warteschlange mit einem "Set-like" Verhalten zu haben, weil Sie einfach keine doppelten Einträge akzeptieren wollen, dann könnte eine einfache Lösung sein, die PriorityQueue abzulösen und die% co_de zu überschreiben %, add() und addAll() Methoden wie:
BTW - offer() ruft add() intern auf, vielleicht ist es sogar genug, die Methode offer() einfach zu überschreiben und die Überprüfung dort durchzuführen.
TreeSet ist ein Satz, der ein geordneter Iterator. Es implementiert die SortedSet Schnittstelle, die garantiert, dass die Der von der Methode iterator zurückgegebene Iterator gibt die Elemente des Satzes in aufsteigender Reihenfolge zurück, die entweder durch ihre natürliche Reihenfolge (durch Comparable ) oder durch einen Komparator bestimmt werden, der dem Satz bei seiner Erstellung gegeben wird.
Nun, die PriorityQueue wird selbst abhängig sein von der Comparitor oder der natürlichen Reihenfolge der Elemente für ihre Sortierung, ebenso wäre die Set abhängig von der natürlichen Ordnung oder der Comparitor Funktion also nein Ich glaube nicht, dass es einen Teil der Java-Standardinstallation gibt ...
Aber Sie könnten wahrscheinlich eine ziemlich einfach erstellen, wenn Geschwindigkeit keine Sorge ist, indem Sie einfach die gewünschten Schnittstellen implementieren und ihre natürlichen Backings usw. verwenden ... aka
%Vor%Leider sind Javas java.util. * -Datensatzklassen nicht immer am einfachsten zu erweitern, ohne Teile ihres Codes neu zu schreiben.
Das PriorityQueue Backing ist eine heap-sortierte Liste von Elementen, so dass ein neues Element eingefügt wird und dann ein contains(e) test eine O (n) Suche durchführt, da die Sortierung auf der Warteschlange basiert, nicht auf dem Datenwert, wenn Sie ein HashSet zur Unterstützung der Funktionalität Set einschließen, können Sie Ihre Nachschlagezeit auf Kosten der doppelten Verwaltung der Datasetverweise erheblich verbessern (denken Sie daran, dass Java pass-by-value ist) und alle Objekte leben auf dem Haufen). Dies sollte die Leistung eines großen Satzes verbessern.
PriorityQueue ist eine AbstractCollection - diese hat eine fast identische Schnittstelle zu einem Set. Ich bin mir sicher, dass es einfach wäre, einen Wrapper zu erstellen, der eine PriorityQueue in ein Set konvertiert. Sie können eine Side-Hash-Tabelle von eingefügten Elementen behalten, um Duplikate zu vermeiden, wenn Sie das wirklich erzwingen müssen.
Ich glaube nicht, dass PriorityQueue comparisonTo konsistent mit equals erfordert. PriorityQueue verwendet überhaupt keine equals (mit Ausnahme der geerbten AbstractCollection-Operationen?).
Tags und Links java queue set priority-queue