Collection triée en Java

Question

Je suis un débutant en Java. Veuillez me suggérer quelle(s) collection(s) peut/doivent être utilisée(s) pour maintenir une liste triée en Java. J'ai essayé Map et Set mais ce n'était pas ce que je recherchais.

Answer 1

Cela arrive très tard, mais il existe une classe dans le JDK qui permet d'obtenir une liste triée. Elle s'appelle (un peu en décalage avec les autres classes de la famille Sorted* interfaces) " java.util.PriorityQueue ". Il peut trier soit Comparable<?> ou en utilisant un Comparator .

La différence avec un List triés en utilisant Collections.sort(...) est qu'elle maintiendra l'ordre à tout moment et offrira de bonnes performances d'insertion grâce à l'utilisation d'une structure de données en tas, où l'insertion dans une structure de données triée est possible. ArrayList sera O(n) (c'est-à-dire en utilisant la recherche binaire et le déplacement).

Toutefois, à l'exception de List , PriorityQueue ne prend pas en charge l'accès indexé ( get(5) ), la seule façon d'accéder aux éléments d'un tas est de les sortir, un par un (d'où le nom de PriorityQueue ).

Answer 2

TreeMap et TreeSet vous donneront une itération sur le contenu dans un ordre trié. Vous pouvez aussi utiliser une ArrayList et utiliser Collections.sort() pour la trier. Toutes ces classes se trouvent dans java.util

Answer 3

Utilisez le TreeMultiset de Google Guava. Guava est une API de collections spectaculaire.

Goyave : http://code.google.com/p/guava-libraries/

TreeMultiset : http://docs.guava-libraries.googlecode.com/git-history/master/javadoc/index.html

Un problème pour fournir une implémentation de List qui maintient l'ordre de tri est la promesse faite dans les Javadocs de la méthode 'add'.

Answer 4

Si vous voulez maintenir un liste triée que vous allez modifier fréquemment (c'est-à-dire une structure qui, en plus d'être triée, autorise les doublons et dont les éléments peuvent être référencés efficacement par index), utilisez une ArrayList mais lorsque vous devez insérer un élément, utilisez toujours Collections.binarySearch() pour déterminer l'indice à laquelle vous ajoutez un élément donné. Cette dernière méthode vous indique l'indice auquel vous devez insérer l'élément pour que votre liste reste dans l'ordre de tri.

Answer 5

Vous voulez le SortedSet les mises en œuvre, à savoir Ensemble d'arbres .