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?
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:
- il rompt le contrat que
List<E>
interface a parce que les méthodesadd
devraient s'assurer que l'élément résidera dans l'index que l'utilisateur spécifie. - 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.
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.
é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 ensemblesn'ont pas cette information.
si vous voulez commander en ajoutant heure, utilisez List
. Si vous souhaitez commander par d'autres critères, utiliser SortedSet
.
Set et Map sont non-linéaire de la structure de données. List est une structure de données linéaire.
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 deTreeList
(c'est à dire pas deSortedList
). - 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.
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.
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
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
.
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.
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.
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.