Pourquoi N'y a-t-il pas de SortedList dans Java?

en Java il y a les interfaces SortedSet et SortedMap . Les deux appartiennent au cadre de Collections standard de Java et fournissent une façon triée d'accéder aux éléments.

cependant, à mon avis, il n'y a pas de SortedList en Java. Vous pouvez utiliser java.util.Collections.sort() pour trier une liste.

vous savez pourquoi il est conçu comme ça?

409
demandé sur rmoestl 2012-01-04 14:35:53

10 réponses

les itérateurs de liste garantissent avant tout que vous obtenez les éléments de la liste dans l'ordre interne de la liste (alias. ordre d'insertion ). Plus précisément, c'est dans l'ordre que vous avez inséré les éléments ou sur la façon dont vous avez manipulé la liste. Le tri peut être considéré comme une manipulation de la structure des données, et il existe plusieurs façons de trier la liste.

je vais ordonner les voies dans l'ordre de utilité comme je personnellement voir:

1. Envisager d'utiliser Set ou Bag collections plutôt

NOTE: je mets cette option en haut parce que c'est ce que vous voulez normalement faire de toute façon.

un ensemble trié trie automatiquement la collection à l'insertion , ce qui signifie qu'il fait le tri pendant que vous ajoutez des éléments dans la collection. Cela signifie également que vous n'avez pas besoin d'manuellement de tri.

en outre, si vous êtes sûr que vous n'avez pas besoin de vous soucier (ou d'avoir) des éléments dupliqués, vous pouvez utiliser le TreeSet<T> à la place. Il implémente les interfaces SortedSet et NavigableSet et fonctionne comme on peut s'y attendre d'une liste:

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"

si vous ne voulez pas l'ordre naturel, vous pouvez utiliser le paramètre constructeur qui prend un Comparator<T> .

alternativement, vous pouvez utiliser Multisets (aussi connu sous le nom sacs ) , c'est-à-dire un Set qui permet des éléments en double, à la place et il ya des implémentations de tiers de ceux-ci. Plus particulièrement de la bibliothèques de la goyave Il ya un TreeMultiset , ça ressemble beaucoup au TreeSet .

2. Trier votre liste Collections.sort()

comme indiqué ci-dessus, le tri de List s est une manipulation de la structure des données. Donc, pour les situations où vous avez besoin "d'une source de vérité" qui sera triée de diverses façons, alors le tri manuel est la voie à suivre.

vous pouvez trier votre liste avec la méthode java.util.Collections.sort() . Voici un exemple de code sur comment:

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"

utilisant des comparateurs

un avantage évident est que vous pouvez utiliser Comparator dans la méthode sort . Java fournit également quelques implémentations pour le Comparator comme le Collator qui est utile pour les chaînes de tri sensibles à la localisation. Voici un exemple:

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

Collections.sort(strings, usCollator);

tri dans des environnements concurrents

notez cependant que l'utilisation de la méthode sort n'est pas conviviale en environnements concurrents, puisque l'instance collection sera manipulée, et vous devriez envisager d'utiliser des collections immuables à la place. C'est quelque chose que la goyave fournit dans la classe Ordering et est une simple doublure:

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

3. Enveloppez votre liste avec java.util.PriorityQueue

bien qu'il n'y ait pas de liste triée en Java, il y a cependant une file d'attente triée qui fonctionnerait probablement aussi bien pour vous. C'est le java.util.PriorityQueue de la classe.

Nico Haase lié dans les commentaires à une question connexe qui répond également à cette question.

dans une collection triée vous ne voulez probablement pas manipuler la structure de données interne qui est pourquoi PriorityQueue ne met pas en œuvre l'interface de liste (parce que cela vous donnerait un accès direct à ses éléments).

mise en garde sur le PriorityQueue itérateur

la classe PriorityQueue implémente les interfaces Iterable<E> et Collection<E> pour qu'elle puisse être itérée comme d'habitude. Cependant, l'itérateur n'est pas garanti de retourner les éléments dans l'ordre trié. Au lieu de cela (comme le souligne Alderath dans les commentaires) vous devez poll() la file d'attente jusqu'à vide.

notez que vous pouvez convertir une liste en file d'attente prioritaire via le constructeur qui prend n'importe quelle collection :

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. Écrivez votre propre SortedList classe

NOTE: vous ne devriez pas avoir à faire cela.

vous pouvez écrire votre propre classe de liste qui trie chaque fois que vous ajoutez un nouvel élément. Cela peut devenir assez lourd de calcul en fonction de votre mise en œuvre et est inutile , sauf si vous voulez le faire comme un exercice, en raison de deux raisons principales:

  1. il rompt le contrat que List<E> interface a parce que les méthodes add devraient s'assurer que l'élément résidera dans l'index que l'utilisateur spécifie.
  2. Pourquoi réinventer la roue? Vous devriez utiliser le TreeSet ou Multisets à la place comme indiqué dans le premier point ci-dessus.

Cependant, si vous voulez faire cela comme un exercice voici un exemple de code pour vous aider à démarrer, il utilise la AbstractList classe abstraite:

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();
    }

}

notez que si vous n'avez pas dépassé les méthodes dont vous avez besoin, alors les implémentations par défaut de AbstractList lanceront UnsupportedOperationException S.

567
répondu Spoike 2018-07-30 15:41:59

parce que la notion de liste est incompatible avec celle de collection triée automatiquement. Le point d'une liste est qu'après avoir appelé list.add(7, elem) , un appel à list.get(7) retournera elem . Avec un auto-liste triée, l'élément pourrait se retrouver dans une position arbitraire.

52
répondu Michael Borgwardt 2012-01-04 10:44:59

étant donné que toutes les listes sont déjà" triées "par ordre d'ajout (ordre FIFO), vous pouvez les" utiliser "avec un autre ordre, y compris l'ordre naturel des éléments, en utilisant java.util.Collections.sort() .

EDIT:

les listes comme les structures de données sont basées dans ce qui est intéressant est l'ordre dans lequel les éléments ont été insérés.

Les ensembles

n'ont pas cette information.

si vous voulez commander en ajoutant heure, utilisez List . Si vous souhaitez commander par d'autres critères, utiliser SortedSet .

22
répondu SJuan76 2018-07-30 16:40:53

Set et Map sont non-linéaire de la structure de données. List est une structure de données linéaire.

enter image description here


L'arbre de la structure de données SortedSet et SortedMap interfaces de mise en œuvre des TreeSet et TreeMap respectivement à l'aide de utilisés Rouge-l'arbre Noir la mise en œuvre de l'algorithme. Afin de s'assurer qu'il n'y a pas d'articles dupliqués (ou des clés dans affaire Map ).

  • List maintient déjà une collecte ordonnée et une structure de données basée sur l'indice, les arbres ne sont pas des structures de données basées sur l'indice.
  • Tree par définition, ne peut pas contenir de doublons.
  • Dans List nous pouvons avoir des doublons, donc il n'y a pas de TreeList (c'est à dire pas de SortedList ).
  • list maintient les éléments dans l'ordre d'insertion. Donc, si nous voulons trier la liste, nous devons utiliser java.util.Collections.sort() . Il trie la liste dans l'ordre croissant, selon l'ordre naturel des éléments.
12
répondu Premraj 2018-05-27 10:47:30

pour tous les nouveaux venus, à partir d'avril 2015, Android a maintenant un Sortlist classe dans la bibliothèque de soutien, conçu spécifiquement pour travailler avec RecyclerView . Voici le post de blog à ce sujet.

9
répondu Amagi82 2015-06-10 19:49:49

JavaFX SortedList

bien que cela ait pris un certain temps, Java 8 a un List trié . http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

comme vous pouvez le voir dans les javadocs, il fait partie des collections JavaFX , destiné à fournir une vue triée sur une liste observable.

mise à jour: notez qu'avec Java 11, Le JavaFX toolkit a quitté le JDK et est maintenant une bibliothèque séparée. JavaFX 11 est disponible sous forme de SDK téléchargeable ou sur MavenCentral. Voir https://openjfx.io

7
répondu swpalmer 2018-09-24 22:52:57

un autre point est la complexité temporelle des opérations d'insertion. Pour une liste insérer, on s'attend à une complexité de O(1). Mais cela ne pouvait pas être garantie avec une liste triée.

et le point le plus important est que les listes ne supposent rien au sujet de leurs éléments. Par exemple, vous pouvez faire des listes de choses qui n'implémentent pas equals ou compare .

4
répondu Ingo 2012-01-04 13:50:44

pensez - y comme ceci: l'interface List a des méthodes comme add(int index, E element) , set(int index, E element) . Le contrat est qu'une fois que vous avez ajouté un élément à la position X, vous le trouverez à moins que vous n'ajoutiez ou supprimiez des éléments avant.

si une implémentation de liste stockerait des éléments dans un ordre autre que celui basé sur l'index, les méthodes de liste ci-dessus n'auraient aucun sens.

3
répondu Costi Ciudatu 2012-01-04 10:47:38

la première ligne de l'API de liste indique qu'il s'agit d'une collection ordonnée (également appelée séquence). Si vous triez la liste, vous ne pouvez pas maintenir l'ordre, il n'y a donc pas de TreeList à Java.

Comme L'API dit Java List s'est inspiré de Sequence et voir les propriétés sequence http://en.wikipedia.org/wiki/Sequence_ (mathématiques )

cela ne signifie pas que vous ne pouvez pas trier la liste, mais Java strict à sa définition et ne fournir des versions triées des listes par défaut.

2
répondu Syam 2012-07-23 06:34:43

envisager d'utiliser arbre-carte indexée . C'est un TreeSet amélioré de JDK qui permet d'accéder à l'élément par index et de trouver l'index d'un élément sans itération ou listes sous-jacentes cachées qui sauvegardent l'arbre. L'algorithme est basé sur la mise à jour des poids des noeuds changeants chaque fois qu'il y a un changement.

1
répondu Vitaly Sazanovich 2014-01-27 14:32:07