Warum gibt es in Java keine SortedList?

Question

In Java gibt es die SortedSet y SortedMap Schnittstellen. Beide gehören zu den Java Collections-Framework und bieten einen geordneten Zugang zu den Elementen.

Nach meinem Verständnis gibt es jedoch keine SortedList in Java. Sie können verwenden java.util.Collections.sort() um eine Liste zu sortieren.

Haben Sie eine Idee, warum sie so gestaltet ist?

Answer 1

Listen-Iteratoren garantieren in erster Linie, dass Sie die Elemente der Liste in der internen Reihenfolge der Liste erhalten (aka. Einfügeauftrag ). Genauer gesagt geht es um die Reihenfolge, in der Sie die Elemente eingefügt haben, oder darum, wie Sie die Liste manipuliert haben. Das Sortieren kann als eine Manipulation der Datenstruktur betrachtet werden, und es gibt mehrere Möglichkeiten, die Liste zu sortieren.

Ich ordne die Wege in der Reihenfolge von Nützlichkeit wie ich es persönlich sehe:

1. Erwägen Sie die Verwendung Set o Bag Sammlungen stattdessen

HINWEIS: Ich habe diese Option an den Anfang gestellt, weil Sie dies normalerweise ohnehin tun wollen.

Eine sortierte Menge sortiert die Sammlung automatisch beim Einfügen Das bedeutet, dass es die Sortierung vornimmt, während Sie der Sammlung Elemente hinzufügen. Das bedeutet auch, dass Sie sie nicht manuell sortieren müssen.

Wenn Sie sicher sind, dass Sie sich keine Sorgen über doppelte Elemente machen müssen (oder solche haben), können Sie außerdem die TreeSet<T> stattdessen. Sie implementiert SortedSet y NavigableSet Schnittstellen und funktioniert so, wie man es von einer Liste erwarten würde:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Wenn Sie die natürliche Reihenfolge nicht wünschen, können Sie den Konstruktorparameter verwenden, der eine Comparator<T> .

Alternativ können Sie auch Multisets (auch bekannt als Taschen ) das ist ein Set die stattdessen doppelte Elemente zulässt, und es gibt Implementierungen von Drittanbietern dafür. Vor allem von der Guava-Bibliotheken gibt es eine TreeMultiset die ähnlich funktioniert wie die TreeSet .

2. Sortieren Sie Ihre Liste mit Collections.sort()

Wie bereits erwähnt, ist die Sortierung von List s ist eine Manipulation der Datenstruktur. In Situationen, in denen Sie "eine einzige Quelle der Wahrheit" benötigen, die auf verschiedene Weise sortiert werden soll, ist die manuelle Sortierung der richtige Weg.

Sie können Ihre Liste mit der Funktion java.util.Collections.sort() Methode. Hier ist ein Code-Beispiel dafür:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Verwendung von Komparatoren

Ein klarer Vorteil ist, dass Sie Folgendes nutzen können Comparator において sort Methode. Java bietet auch einige Implementierungen für die Comparator wie zum Beispiel die Collator was für die Sortierung von Zeichenketten nach Gebietsschema nützlich ist. Hier ist ein Beispiel:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Sortierung in konkurrierenden Umgebungen

Beachten Sie jedoch, dass die Verwendung des sort Methode ist in konkurrierenden Umgebungen nicht freundlich, da die Sammlungsinstanz manipuliert wird, und Sie sollten stattdessen unveränderliche Sammlungen verwenden. Dies ist etwas, das Guava in der Ordering Klasse und ist ein einfacher Einzeiler:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Umschließen Sie Ihre Liste mit java.util.PriorityQueue

Obwohl es in Java keine sortierte Liste gibt, gibt es doch eine sortierte Warteschlange, die wahrscheinlich genauso gut für Sie funktionieren würde. Es ist die java.util.PriorityQueue Klasse.

Nico Haase hat in den Kommentaren auf eine zugehörige Frage die auch diese Frage beantwortet.

In einer sortierten Sammlung Sie wollen höchstwahrscheinlich nicht manipulieren die interne Datenstruktur, weshalb PriorityQueue die Schnittstelle List nicht implementiert (denn dann hätte man direkten Zugriff auf ihre Elemente).

Vorbehalt gegen die PriorityQueue Iterator

Le site PriorityQueue Klasse implementiert die Iterable<E> y Collection<E> Schnittstellen, so dass sie wie üblich iteriert werden kann. Es ist jedoch nicht garantiert, dass der Iterator Elemente in der sortierten Reihenfolge zurückgibt. Stattdessen (wie Alderath in den Kommentaren anmerkt) müssen Sie poll() die Warteschlange, bis sie leer ist.

Beachten Sie, dass Sie eine Liste in eine Prioritätswarteschlange umwandeln können, indem Sie die Konstruktor, der eine beliebige Sammlung annimmt :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Schreiben Sie Ihr eigenes SortedList クラス

HINWEIS: Sie sollten das nicht tun müssen.

Sie können Ihre eigene Listenklasse schreiben, die jedes Mal sortiert, wenn Sie ein neues Element hinzufügen. Dies kann je nach Implementierung ziemlich rechenintensiv werden und ist sinnlos Es sei denn, Sie wollen es als Übung machen, und zwar aus zwei Gründen:

1. Es bricht den Vertrag, der List<E> Schnittstelle hat, weil die add Methoden sollten sicherstellen, dass sich das Element in dem vom Benutzer angegebenen Index befindet.
2. Warum das Rad neu erfinden? Sie sollten stattdessen das TreeSet oder Multisets verwenden, wie im ersten Punkt oben beschrieben.

Wenn Sie es jedoch als Übung machen wollen, finden Sie hier ein Codebeispiel, das Ihnen den Einstieg erleichtern soll; es verwendet die AbstractList abstrakte Klasse:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Beachten Sie, dass, wenn Sie die benötigten Methoden nicht überschrieben haben, die Standardimplementierungen von AbstractList wirft UnsupportedOperationException s.

Answer 2

Denn das Konzept einer Liste ist mit dem Konzept einer automatisch sortierten Sammlung unvereinbar. Der Sinn einer Liste ist, dass nach dem Aufruf von list.add(7, elem) einen Aufruf an list.get(7) wird zurückgegeben elem . Bei einer automatisch sortierten Liste könnte das Element an einer beliebigen Position landen.

Answer 3

Da alle Listen bereits in der Reihenfolge "sortiert" sind, in der die Elemente hinzugefügt wurden (FIFO-Reihenfolge), können Sie sie mit einer anderen Reihenfolge "sortieren", einschließlich der natürlichen Reihenfolge der Elemente, indem Sie java.util.Collections.sort() .

EDIT :

Listen als Datenstrukturen beruhen auf der Reihenfolge, in der die Elemente eingefügt wurden, was interessant ist.

Die Sets haben diese Informationen nicht.

Wenn Sie eine Bestellung mit Zeitangabe aufgeben möchten, verwenden Sie List . Wenn Sie nach anderen Kriterien sortieren möchten, verwenden Sie SortedSet .

Answer 4

Set und Map sind nicht-lineare Datenstrukturen. Liste ist eine lineare Datenstruktur.

---

Die Baumdatenstruktur SortedSet y SortedMap Schnittstellen implementiert TreeSet y TreeMap jeweils unter Verwendung der verwendeten Rot-schwarzer Baum Implementierungsalgorithmus. So wird sichergestellt, dass es keine doppelten Elemente (oder Schlüssel im Falle von Map ).

• List bereits eine geordnete Sammlung und eine indexbasierte Datenstruktur unterhält, sind Bäume keine indexbasierten Datenstrukturen.
• Tree können per Definition keine Duplikate enthalten.
• Unter List können wir Duplikate haben, also gibt es keine TreeList (d.h. keine SortedList ).
• Die Liste behält die Elemente in der Einfügereihenfolge bei. Wenn wir also die Liste sortieren wollen, müssen wir java.util.Collections.sort() . Es sortiert die angegebene Liste in aufsteigender Reihenfolge, entsprechend der natürlichen Reihenfolge ihrer Elemente.

Answer 5

JavaFX SortedList

Auch wenn es eine Weile gedauert hat, hat Java 8 eine sortierte List . http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Wie Sie in den Javadocs sehen können, ist es Teil der JavaFX Sammlungen, die eine sortierte Ansicht auf eine ObservableList bieten sollen.

Update: Beachten Sie, dass mit Java 11 das JavaFX-Toolkit aus dem JDK ausgegliedert wurde und nun eine separate Bibliothek ist. JavaFX 11 ist als herunterladbares SDK oder von MavenCentral erhältlich. Siehe https://openjfx.io