Pourquoi n’y a-t-il pas de SortedList dans Java?

En Java, il existe les interfaces SortedMap et SortedMap . Les deux appartiennent au framework de collections standard de Java et fournissent une manière sortingée d’accéder aux éléments.

Cependant, à ma connaissance, il n’y a pas de liste SortedList en Java. Vous pouvez utiliser java.util.Collections.sort() pour sortinger une liste.

Une idée de pourquoi c’est conçu comme ça?

Les iterators de listes 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 dans lequel vous avez inséré les éléments ou sur la manière dont vous avez manipulé la liste. Le sorting peut être considéré comme une manipulation de la structure de données et il existe plusieurs manières de sortinger la liste.

Je vais commander les moyens dans l’ordre d’ utilité comme je le vois personnellement:

1. Envisagez d’utiliser des collections Set ou Bag la place

NOTE: Je mets cette option en haut car c’est ce que vous voulez normalement faire de toute façon.

Un ensemble sortingé sortinge automatiquement la collection à l’insertion , ce qui signifie qu’elle effectue le sorting pendant que vous ajoutez des éléments à la collection. Cela signifie également que vous n’avez pas besoin de le sortinger manuellement.

De plus, si vous êtes sûr de ne pas avoir à vous soucier (ou d’avoir) des éléments en double, vous pouvez utiliser le TreeSet place. Il implémente les interfaces SortedSet et NavigableSet et fonctionne comme vous vous en doutez probablement dans une liste:

 TreeSet set = new TreeSet(); set.add("lol"); set.add("cat"); // automatically sorts natural order when adding for (Ssortingng 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 .

Vous pouvez également utiliser Multisets (également appelés Bags ) , c’est-à-dire un Set qui autorise les éléments en double, et il en existe des implémentations tierces. Plus particulièrement des bibliothèques de goyave, il y a un TreeMultiset , qui fonctionne beaucoup comme le TreeSet .

2. Trier votre liste avec Collections.sort()

Comme mentionné ci-dessus, le sorting de List s est une manipulation de la structure de données. Donc, pour les situations où vous avez besoin d’une “source de vérité” qui sera sortingée de diverses manières, le sorting manuel est la solution.

Vous pouvez sortinger votre liste avec la méthode java.util.Collections.sort() . Voici un exemple de code expliquant comment:

 List ssortingngs = new ArrayList() ssortingngs.add("lol"); ssortingngs.add("cat"); Collections.sort(ssortingngs); for (Ssortingng s : ssortingngs) { System.out.println(s); } // Prints out "cat" and "lol" 

Utiliser des comparateurs

Un avantage évident est que vous pouvez utiliser Comparator dans la méthode de sort . Java fournit également des implémentations pour le Comparator telles que Collator qui est utile pour les chaînes de sorting sensibles aux parameters régionaux. Voici un exemple:

 Collator usCollator = Collator.getInstance(Locale.US); usCollator.setStrength(Collator.PRIMARY); // ignores casing Collections.sort(ssortingngs, usCollator); 

Tri dans des environnements concurrents

Notez que l’utilisation de la méthode de sort n’est pas conviviale dans les environnements concurrents, car l’instance de la collection sera manipulée et vous devriez envisager d’utiliser plutôt des collections immuables. C’est quelque chose que Guava fournit dans la classe Ordering et qui est simple:

 List sorted = Ordering.natural().sortedCopy(ssortingngs); 

3. Emballez votre liste avec java.util.PriorityQueue

Bien qu’il n’y ait pas de liste sortingée en Java, il y a cependant une queue sortingée qui fonctionnerait probablement aussi bien pour vous. C’est la classe java.util.PriorityQueue .

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

Dans une collection sortingée, vous ne souhaiterez probablement pas manipuler la structure de données interne. C’est pourquoi PriorityQueue n’implémente pas l’interface List (car cela vous donnerait un access direct à ses éléments).

Mise en garde sur l’iterator PriorityQueue

La classe PriorityQueue implémente les interfaces Iterable et Collection afin qu’elle puisse être itérée comme d’habitude. Cependant, il n’est pas garanti que l’iterator renvoie des éléments dans l’ordre sortingé. Au lieu de cela (comme Alderath le souligne dans les commentaires), vous devez poll() la queue jusqu’à ce qu’elle soit vide.

Notez que vous pouvez convertir une liste en queue prioritaire via le constructeur qui prend n’importe quelle collection :

 List ssortingngs = new ArrayList() ssortingngs.add("lol"); ssortingngs.add("cat"); PriorityQueue sortedSsortingngs = new PriorityQueue(ssortingngs); while(!sortedSsortingngs.isEmpty()) { System.out.println(sortedSsortingngs.poll()); } // Prints out "cat" and "lol" 

4. Ecrivez votre propre classe SortedList

NOTE: Vous ne devriez pas avoir à faire cela.

Vous pouvez écrire votre propre classe List qui sortinge chaque fois que vous ajoutez un nouvel élément. Cela peut être plutôt lourd en calcul en fonction de votre implémentation et est inutile , à moins que vous vouliez le faire en tant qu’exercice, pour deux raisons principales:

  1. Il rompt le contrat de l’interface List , car les méthodes add doivent garantir que l’élément réside dans l’index spécifié par l’utilisateur.
  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 le faire comme exercice, voici un exemple de code pour vous aider à démarrer, il utilise la classe abstraite AbstractList :

 public class SortedList extends AbstractList { private ArrayList internalList = new ArrayList(); // 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 remplacé les méthodes dont vous avez besoin, les implémentations par défaut de AbstractList lancent UnsupportedOperationException s.

Parce que le concept d’une liste est incompatible avec le concept d’une collection sortingée automatiquement. Le point d’une liste est qu’après l’appel de list.add(7, elem) , un appel à list.get(7) renverra elem . Avec une liste sortingée automatiquement, l’élément pourrait se retrouver dans une position arbitraire.

Comme toutes les listes sont déjà “sortingées” selon l’ordre dans lequel les éléments ont été ajoutés (classement FIFO), vous pouvez les “utiliser” avec un autre ordre, y compris l’ordre naturel des éléments, en utilisant java.util.Collections.sort() .

MODIFIER:

Les listes en tant que structures de données sont basées sur ce qui est intéressant, c’est-à-dire l’ordre dans lequel les éléments ont été insérés.

Les ensembles n’ont pas cette information.

Si vous souhaitez commander en ajoutant du temps, utilisez la List . Si vous souhaitez commander selon d’autres critères, utilisez SortedSet .

Set et Map sont des structures de données non linéaires. La liste est une structure de données linéaire.

entrer la description de l'image ici


La structure de données arborescente Les interfaces SortedMap et SortedMap implémentent respectivement TreeSet et TreeMap utilisant l’algorithme d’implémentation de l’ arborescence Red-Black . Ainsi, il n’y a pas d’éléments dupliqués (ou de clés en cas de Map ).

  • List is gère déjà une collection ordonnée et une structure de données basée sur un index, les arborescences ne sont pas des structures de données basées sur des index.
  • 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 (pas de SortedList ).
  • La liste conserve les éléments dans l’ordre d’insertion. Donc, si nous voulons sortinger la liste, nous devons utiliser java.util.Collections.sort() . Il sortinge la liste spécifiée en ordre croissant, en fonction de l’ordre naturel de ses éléments.

Pour les nouveaux venus, à compter d’avril 2015, Android dispose désormais d’une classe SortedList dans la bibliothèque de support, spécialement conçue pour fonctionner avec RecyclerView . Voici le blog à ce sujet.

JavaFX SortedList

Bien que cela ait pris du temps, Java 8 a une List sortingée. 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ées à fournir une vue sortingée sur une ObservableList.

Un autre point est la complexité temporelle des opérations d’insertion. Pour un insert de liste, on s’attend à une complexité de O (1). Mais cela ne pouvait pas être garanti avec une liste sortingée.

Et le point le plus important est que les listes ne supposent rien sur leurs éléments. Par exemple, vous pouvez créer des listes de choses qui ne sont pas equals ou compare .

Pensez à ceci: l’interface List a des méthodes comme add(int index, E element) , set(int index, E element) . Le contrat stipule qu’une fois que vous avez ajouté un élément à la position X, vous le trouverez à moins d’append ou de supprimer des éléments avant.

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

La première ligne de l’API List indique qu’il s’agit d’une collection ordonnée (également appelée séquence). Si vous sortingez la liste, vous ne pouvez pas conserver la commande, il n’y a donc pas de liste TreeList dans Java.
Comme API dit Java List a été inspiré de Sequence et voir les propriétés de la séquence http://en.wikipedia.org/wiki/Sequence_(mathematics )

Cela ne signifie pas que vous ne pouvez pas sortinger la liste, mais Java ssortingctement selon sa définition et ne fournit pas de versions sortingées des listes par défaut.

Pensez à utiliser la carte indexée . C’est un TreeSet de JDK amélioré qui permet d’accéder à element par index et de trouver l’index d’un élément sans itération ni liste sous-jacente masquée qui sauvegarde l’arborescence. L’algorithme est basé sur la mise à jour des poids des nœuds changeants chaque fois qu’il y a un changement.