Listenimplementierung, die die Bestellung beibehält

Question

Gibt es in Java eine List Implementierung, die die Reihenfolge basierend auf der bereitgestellten Comparator verwaltet?

Etwas, das in der folgenden Art und Weise verwendet werden kann:

Comparator<T> cmp = new MyComparator<T>(); 
List<T> l = new OrderedList<T>(cmp); 
l.add(someT); 

so dass someT wird so eingesetzt, dass die Reihenfolge in der Liste beibehalten wird nach cmp

(On @andersoj Vorschlag, den ich bin Abschluss meine Frage mit einer weiteren Anfrage)

Auch ich möchte in der Lage sein, die Liste in sortierter Reihenfolge durchlaufen, ohne die Elemente zu entfernen, dh:

T min = Const.SMALLEST_T; 
for (T e: l) { 
    assertTrue(cmp.compare(min, e) >= 0); 
    min = e; 
} 

sollte übergeben werden.

Alle Vorschläge sind willkommen (außer mir zu sagen, Collections.sort auf der ungeordneten vollständige Liste zu verwenden), aber ich würde etwas in java.* oder schließlich org.apache.* bevorzugen, da es schwierig sein würde, neue Bibliotheken zu diesem Zeitpunkt einzuführen.

Anmerkung: (Update4) Ich erkannte, dass Implementierungen dieser Art von Liste unzureichende Leistung haben würde. Es zwei allgemeine Ansätze:

1. Verwenden verknüpfte Struktur (Art von) B-Baum oder ähnliche
2. Verwenden Array und Insertion (mit Binärsuche)

No 1. hat Problem mit CPU Cache-Misses Nein 2. hat Probleme mit dem Verschieben von Elementen im Array.

UPDATE2: TreeSet funktioniert nicht, weil sie den vorgesehenen Komparator (MyComparator) verwendet für die Gleichstellung zu überprüfen und basierend darauf setzt voraus, dass die Elemente gleich sind und sie auszuschließen. Ich brauche diesen Komparator nur für die Bestellung, nicht „Einzigartigkeit“ Filterung (da die Elemente durch ihre natürliche Ordnung nicht gleich sind)

UPDATE3: PriorityQueue nicht als List funktioniert (wie ich brauche), weil es Es gibt keine Möglichkeit, sie in der Reihenfolge zu durchlaufen, in der sie "sortiert" ist. Um die Elemente in der sortierten Reihenfolge zu erhalten, müssen Sie sie aus der Sammlung entfernen.

UPDATE:

ähnliche Frage:
A good Sorted List for Java
Sorted array list in Java

Answer 1

Antwort auf neue Anforderung. Ich sehe zwei Potentiale:

• Tun Sie, was die JavaDoc für PriorityQueue sagt:

  Diese Klasse und ihre Iterator implementieren alle optionalen Methoden der Sammlung und Iterator-Schnittstellen. Der Iterator, der in der Methode iterator() bereitgestellt wird, ist nicht garantiert, die Elemente der Prioritätswarteschlange in einer bestimmten Reihenfolge zu durchlaufen. Wenn Sie eine geordnete Überquerung benötigen, sollten Sie die Verwendung von Arrays.sort(pq.toArray()) in Erwägung ziehen.

  Ich vermute, dass dies die beste Leistung bei Ihren Anforderungen ergibt. Wenn dies nicht akzeptabel ist, müssen Sie besser erklären, was Sie erreichen möchten.

• Erstellen Sie eine Liste, die sich beim Hinzufügen neuer Elemente einfach sortiert. Das ist ein echter Schmerz ... Wenn Sie eine verknüpfte Struktur verwenden, können Sie eine effiziente Einfügesortierung durchführen, aber die Lokalität ist schlecht. Wenn Sie eine Array-Backed-Struktur verwenden, ist das Einfügen von Sortierung ein Problem, aber Traversieren ist besser. Wenn Iteration/Traversal selten ist, könnten Sie den Listeninhalt unsortiert halten und nur bei Bedarf sortieren.

• Betrachten mit einer Priorityqueue wie ich vorgeschlagen, und im Fall müssen Sie, um wiederholen, schreiben Sie einen Iterator-Wrapper:

  class PqIter implements Iterator<T> 
  { 
      final PriorityQueue<T> pq; 
      public PqIter(PriorityQueue <T> source) 
      { 
      pq = new PriorityQueue(source); 
      } 
  
      @Override 
      public boolean hasNext() 
      { 
      return pq.peek() != null 
      } 
  
      @Override 
      public T next() 
      { return pq.poll(); } 
  
      @Override 
      public void remove() 
      { throw new UnsupportedOperationException(""); } 
  } 
  

• Verwenden Guava der TreeMultiSet. Ich testete den folgenden Code mit Integer und es scheint das Richtige zu tun.

  import com.google.common.collect.TreeMultiset; 
  
  public class TreeMultiSetTest { 
      public static void main(String[] args) { 
      TreeMultiset<Integer> ts = TreeMultiset.create(); 
      ts.add(1); ts.add(0); ts.add(2); 
      ts.add(-1); ts.add(5); ts.add(2); 
  
      for (Integer i : ts) { 
       System.out.println(i); 
      } 
      } 
  } 
  

Die unten befasst sich mit der Einmaligkeit/Filterung Problem, das Sie haben wurden, wenn ein SortedSet verwenden. Ich sehe, dass Sie auch einen Iterator wollen, also wird das nicht funktionieren.

Wenn was Sie wirklich wollen, ist eine bestellte list-ähnliche Sache, können Sie eine PriorityQueue verwenden.

Comparator<T> cmp = new MyComparator<T>(); 
PriorityQueue<T> pq = new PriorityQueue<T>(cmp); 
pq.add(someT); 

Beachten Sie, was die API-Dokumentation sagt über die Zeiteigenschaften von verschiedenen Operationen:

Implementierung Hinweis: Diese Implementierung stellt O (log (n)) Zeit für die Enqueing und dequeing Methoden (offer, poll, remove() und add); linear Zeit für die Methoden remove(Object) und contains(Object); und Konstante Zeit für die Abrufmethoden (peek, element und size).

Sie sollten sich auch bewusst sein, dass die von PriorityQueue erzeugt Iteratoren verhalten sich nicht wie man erwarten könnte:

Die Iterator in Verfahren bereitgestellt iterator() nicht die Elemente der Prioritätswarteschlange in jeder zu durchqueren garantiert bestimmte Reihenfolge. Wenn Sie eine geordnete Überquerung benötigen, sollten Sie die Verwendung von Arrays.sort(pq.toArray()) in Erwägung ziehen.

Ich habe gerade festgestellt, dass Guava eine MinMaxPriorityQueue bietet. Diese Implementierung ist Array-Backed und nicht die verknüpfte Form, die in den JDKs PriorityQueue bereitgestellt wird, und hat daher wahrscheinlich ein unterschiedliches Timing-Verhalten. Wenn Sie etwas leistungsempfindliches tun, können Sie einen Blick darauf werfen. Während die Noten leicht unterschiedliche (lineare und logarithmische) Groß-O-Zeiten ergeben, sollten alle diese Zeiten ebenfalls begrenzt sein, was nützlich sein kann.

Es gibt nicht eine List Implementierung per se, die Ordnung hält, aber was Sie wahrscheinlich suchen, sind Implementierungen von SortedSet. A TreeSet ist am häufigsten. Die andere Implementierung, ein ConcurrentSkipListSet, ist für spezifischere Verwendungen. Beachten Sie, dass eine SortedSet Bestellung bietet, aber keine doppelten Einträge erlaubt, ebenso wie eine List.

Refs:

• Blog post PriorityQueue iterator is not ordered
• SO auf PQ ordered iterator

Answer 2

Sie sollen wahrscheinlich ein TreeSet werden:

Die Elemente sind in der Reihenfolge ihrer natürliche Ordnung, oder durch einen Komparator zur festgelegten Erstellungszeit bereitgestellt, abhängig davon, welcher Konstruktor verwendet wird.

Beispiel:

Comparator<T> cmp = new MyComparator<T>(); 
TreeSet<T> t = new TreeSet<T>(cmp); 
l.add(someT); 

Beachten Sie, dass dies ein gesetzt ist, so dass keine doppelten Einträge sind erlaubt. Dies kann für Ihren speziellen Anwendungsfall funktionieren oder nicht.

Answer 3

Frage: Ich habe ein ähnliches Problem und ich denke eine TreeSet zu verwenden. Um "gleiche" Elemente auszuschließen, werde ich den Vergleicher so ändern, dass ich anstelle von 0 eine Zufallszahl zwischen (-1,1) zurückgebe oder immer 1 zurückgebe.

Wenn Sie keine Kontrolle über den Komparator haben oder Wenn Sie es für etwas anderes als das Einfügen dieser Lösung verwenden, funktioniert es nicht für Sie.