Pourquoi il n'y a pas de SortedList en Java?

Question

En Java, il y a SortedSet et SortedMap . Les deux appartiennent à des collections et ont fourni un moyen trié pour accéder aux éléments.

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

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

Answer 1

Liste des itérateurs de garantir d'abord et avant tout que vous obtenez les éléments de la liste dans l'ordre interne de la liste (aka. 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 vu comme une manipulation de la structure de données, et il y a plusieurs façons de trier la liste.

Je vais commander les moyens de l'ordre de l'utilité que personnellement, je vois:

1. Envisagez d'utiliser un Sets ou Bags au lieu

J'ai mis cette option en haut parce que c'est ce que vous souhaitez l'utiliser pour faire de toute façon. Un ensemble trié automatiquement trie la collection au moment de l'insertion, ce qui signifie que vous n'avez pas besoin de les trier manuellement. Si vous êtes sûr que vous n'avez pas besoin de s'inquiéter (ou ont) les éléments en double, vous pouvez utiliser l' TreeSet<T> à la place. Il met en oeuvre SortedSet et NavigableSet interfaces et des travaux que vous auriez probablement attendre:

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 de constructeur qui prend un Comparator<T>.

Alternativement, vous pouvez utiliser Multisets (également connus comme les Sacs), qui est un Ensemble qui permet de dupliquer des éléments, à la place, et il y a des tiers implémentations d'entre eux. Notamment à partir de la Goyave, les bibliothèques il y a un TreeMultiset, qui fonctionne un peu comme le TreeSet.

2. Triez votre liste avec Collections.sort()

Vous pouvez trier votre liste avec l' java.util.Collections.sort() méthode. Voici un exemple de code sur la façon de faire:

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"

3. Enveloppez votre liste avec java.util.PriorityQueue

Bien qu'il n'existe pas de liste triée en Java il y a cependant une triés file d'attente qui serait sans doute tout aussi bien pour vous. C'est l' java.util.PriorityQueue classe.

Nico Haase lié dans les commentaires sur une question connexe, qui répond également présent.

Dans une collection triée vous probablement ne voulez pas manipuler la structure de données interne qui est pourquoi PriorityQueue ne pas mettre en œuvre la Liste de l'interface (parce que ce serait vous donner un accès direct à ses éléments).

Note:

L' PriorityQueue classe implémente l' Iterable<E> et Collection<E> interfaces de sorte qu'il peut être itéré, comme d'habitude. Cependant l'itérateur n'est pas garantie pour renvoyer les éléments dans l'ordre de tri. À la place (comme Alderath points dans les commentaires), vous devrez poll() la file d'attente jusqu'à ce vide.

Notez que vous pouvez convertir une liste d'attente prioritaire par le constructeur qui prend toute la 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

Vous pouvez écrire votre propre Liste de classe qui trie chaque fois que vous ajoutez un nouvel élément. Cela peut devenir un peu de calcul lourds en fonction de votre mise en œuvre, et est du genre inutile, sauf si vous voulez faire cela comme un exercice. J'mention inutile à cause de deux raisons principales:

1. Il casse les promesses qu' List<E> interface a, parce que l' add méthodes devraient veiller à ce que l'élément résider dans l'index qui spécifie l'utilisateur.
2. Pourquoi réinventer la roue? Vous devriez être en utilisant le TreeSet ou Multisets plutôt que comme l'a souligné ci-dessus.

Voici quelques exemples de code pour vous aider à démarrer bien que, il utilise l' 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 de redéfinir les méthodes que vous avez besoin, puis les implémentations par défaut de AbstractList va jeter UnsupportedOperationExceptions.

Answer 2

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

Answer 3

Parce que toutes les listes sont déjà triées par ordre.

Vous pouvez "les utiliser" avec un autre ordre 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 dans l'ordre dans lequel les éléments ont été insérés.

Les ensembles n'ont pas cette information.

Si vous souhaitez commander par temps supplémentaire, utilisez List . Si vous souhaitez commander selon d'autres critères, utilisez SortedSet .

Answer 4

Un autre point est la complexité des opérations d’insertion. Pour un encart de la liste, on s’attend à une complexité d’o (1). Mais cela ne pouvait être garantie avec une liste triée.

Et le point le plus important est que les listes assument rien au sujet de leurs éléments. Par exemple, vous pouvez faire des listes de choses qui n’implémentent pas ou .

Answer 5

Pensez-y comme ceci : la interface possède des méthodes comme , `` . Le contrat, c’est qu’une fois que vous avez ajouté un élément à la position X, vous le trouverez là sauf si vous ajoutez ou supprimez des éléments devant elle.

Si n’importe quelle implémentation de liste serait stocker les éléments dans un ordre autre que basé sur l’indice, les méthodes de la liste ci-dessus seraient insensé.