Maîtriser les collections de fléchettes | Android-Dev

Jusqu’à présent, vous avez vu les collections les plus couramment utilisées sur Dart. Cependant, ce n’est que la pointe de l’iceberg.

Selon le problème que vous essayez de résoudre, vous pouvez choisir une collection avec de meilleures performances.

Liste Liée

Une LinkedList est une liste spécialisée de deux liens d’éléments qui étendent LinkedListEntry.

Malgré son nom, LinkedList n’est pas une implémentation de List, il ne fournit donc pas de recherche d’index en temps constant.

Étant donné que chaque élément LinkedListEntry connaît sa position dans la liste, cela permet un temps constant. insertAfter, insertBefore et unlink opérations sur l’élément LinkedListEntry.

LinkedList permet l’ajout et la suppression de temps constants à chaque extrémité, ainsi qu’un getter de longueur de temps constant.

Ligne

Une file d’attente est une collection qui peut être manipulée des deux côtés.
Puisque Queue est une classe abstraite dans Dart, il existe deux implémentations principales disponibles :

• ListQueue
• DoubleLinkedQueue

ListQueue maintient un tampon cyclique d’éléments. Lorsque le tampon est plein, il double de taille pour accueillir de nouveaux éléments.

Assure des opérations de pointe et de purge à temps constant et un temps constant amorti pour les opérations d’ajout (en raison des ajustements de la taille de la mémoire tampon).

DoubleLinkedQueue est une implémentation de file d’attente basée sur une liste doublement chaînée.

Il permet des opérations d’ajout, de suppression de bord et de coup d’œil constants.

hachage

Un HashSet est une implémentation de table de hachage non ordonnée de Set.

Tous les éléments d’un HashSet doivent avoir une égalité cohérente et hashCode Mise en œuvre.

En fonction de la distribution des codes de hachage des éléments, le add, remove, contains et length les opérations sont exécutées en temps constant potentiellement amorti.

Étant donné que les éléments d’un HashSet ne sont pas ordonnés, l’ordre de l’itération n’est pas spécifié, mais il est cohérent entre les modifications apportées à l’ensemble.

SplayTreeSet

Un SplayTreeSet est une implémentation d’arbre binaire auto-équilibré de Set. Il permet la plupart des opérations en temps logarithmique amorti.

Les éléments de l’ensemble peuvent être ordonnés les uns par rapport aux autres à l’aide d’un compare fonction qui est passée dans le constructeur.

Si la fonction de comparaison est omise, les objets doivent être Comparable et comparé à l’aide de leur Comparable.compareTo méthode.

HashMap

Comme un HashSet, un HashMap est une implémentation de table de hachage non ordonnée de Set.

Les clés d’un HashMap doivent avoir une égalité cohérente et hashCode Mise en œuvre.

Des opérations simples se font en temps constant (potentiellement amorti) : ajouter, contenir, supprimer et longueur, tant que les codes de hachage des objets sont bien répartis.

L’ordre d’itération des clés, des valeurs et des entrées n’est pas spécifié et peut se produire dans n’importe quel ordre, mais il est cohérent d’une modification à l’autre. Les valeurs sont itérées dans le même ordre que leurs clés associées – l’itération des clés et des valeurs en parallèle fournira des paires clé/valeur correspondantes.

SplayTreeMap

Un SplayTreeMap est une implémentation de carte basée sur un arbre binaire auto-équilibré. Il permet d’amortir la plupart des opérations de saisie simple en temps logarithmique.

Les clés de carte sont comparées à l’aide du compare fonction passée dans le constructeur.

Si la fonction de comparaison est omise, les clés sont considérées Comparable et ses associés Comparable.compareTo les fonctions sont utilisées pour définir leur ordre sur la carte.