Partager via

Collections et structures de données

Les données similaires peuvent souvent être gérées plus efficacement lorsqu’elles sont stockées et manipulées en tant que collection. Vous pouvez utiliser la System.Array classe ou les classes dans les System.Collectionsespaces de noms , System.Collections.GenericSystem.Collections.Concurrentet System.Collections.Immutable ajouter, supprimer et modifier des éléments individuels ou une plage d’éléments dans une collection.

Il existe deux types principaux de collections ; collections génériques et collections non génériques. Les collections génériques sont de type sécurisé au moment de la compilation. En raison de cela, les collections génériques offrent généralement de meilleures performances. Les collections génériques acceptent un paramètre de type lorsqu’ils sont construits. Il n’est pas nécessaire d’effectuer de conversion vers ou depuis le type Object lorsque vous ajoutez ou retirez des éléments de la collection. En outre, la plupart des collections génériques sont prises en charge dans les applications du Windows Store. Les collections non génériques stockent les éléments en tant que Object, nécessitent un transtypage, et la plupart ne sont pas prises en charge pour le développement d’applications Windows Store. Toutefois, vous pouvez voir des collections non génériques dans du code plus ancien.

Dans .NET Framework 4 et versions ultérieures, les collections de l'espace de noms System.Collections.Concurrent fournissent des opérations thread-safe efficaces pour accéder aux éléments de collection depuis plusieurs threads. Les classes de collection immuable de l’espace de noms System.Collections.Immutable (NuGet package) sont thread-safe, car les opérations sont effectuées sur une copie de la collection d’origine et celle-ci ne peut donc pas être modifiée.

Fonctionnalités courantes de collection

Toutes les collections fournissent des méthodes pour ajouter, supprimer ou rechercher des éléments dans la collection. En outre, toutes les collections qui implémentent directement ou indirectement l’interface ICollection ou l’interface ICollection<T> partagent ces fonctionnalités :

  • Possibilité d’énumérer la collection

    Les collections .NET implémentent soit System.Collections.IEnumerable soit System.Collections.Generic.IEnumerable<T> pour permettre ainsi à la collection d’être itérée. Un énumérateur peut être considéré comme un pointeur mobile vers n’importe quel élément de la collection. L’instruction foreach, in et For Each...Next Instruction utilisent l’énumérateur exposé par la méthode GetEnumerator et masquent la complexité de la manipulation de l’énumérateur. En outre, toute collection qui implémente System.Collections.Generic.IEnumerable<T> est considérée comme un type interrogeable et peut être interrogée avec LINQ. Les requêtes LINQ fournissent un modèle courant pour accéder aux données. Ils sont généralement plus concis et lisibles que les boucles standard foreach et fournissent des fonctionnalités de filtrage, de classement et de regroupement. Les requêtes LINQ peuvent également améliorer les performances. Pour plus d’informations, consultez LINQ to Objects (C#),LINQ to Objects (Visual Basic),Parallel LINQ (PLINQ), Introduction aux requêtes LINQ (C#) et Opérations de requête de base (Visual Basic).

  • Possibilité de copier le contenu de la collection dans un tableau

    Toutes les collections peuvent être copiées dans un tableau à l’aide de la CopyTo méthode. Toutefois, l’ordre des éléments dans le nouveau tableau est basé sur la séquence dans laquelle l’énumérateur les retourne. Le tableau résultant est toujours unidimensionnel avec une limite inférieure de zéro.

En outre, de nombreuses classes de collection contiennent les fonctionnalités suivantes :

  • Propriétés de capacité et de nombre

    La capacité d’une collection est le nombre d’éléments qu’elle peut contenir. Le compte d'une collection est le nombre total d’éléments qu'elle contient réellement. Certaines collections masquent l'une de ces propriétés, voire les deux.

    La plupart des collections augmentent automatiquement leur capacité lorsque la capacité actuelle est atteinte. La mémoire est réallouée et les éléments sont copiés depuis l'ancienne collection vers la nouvelle. Cette conception réduit le code requis pour utiliser la collection. Toutefois, les performances de la collection peuvent être affectées négativement. Par exemple, pour List<T>, si Count est inférieur à Capacity, l'ajout d'un élément est une opération O(1). Si la capacité doit être augmentée pour prendre en charge le nouvel élément, l’ajout d’un élément devient une opération O(n), où n est Count. La meilleure façon d’éviter les performances médiocres causées par plusieurs réaffectations consiste à définir la capacité initiale pour être la taille estimée de la collection.

    A BitArray est un cas spécial ; sa capacité est la même que sa longueur, qui est la même que son nombre.

  • Une limite inférieure cohérente

    La limite inférieure d’une collection est l’index de son premier élément. Toutes les collections indexées dans les System.Collections espaces de noms ont une limite inférieure de zéro, ce qui signifie qu’elles sont indexées à 0. Array a une limite inférieure de zéro par défaut, mais une limite inférieure différente peut être définie lors de la création d’une instance de la classe Array à l’aide Array.CreateInstancede .

  • Synchronisation pour l’accès à partir de plusieurs threads (System.Collections classes uniquement).

    Les types de collections non génériques de l’espace de noms System.Collections fournissent une certaine cohérence de thread pour la synchronisation, généralement exposée par des membres SyncRoot et IsSynchronized. Ces collections ne sont pas thread-safe par défaut. Si vous avez besoin d'un accès multithread évolutif et efficace pour une collection, utilisez l'une des classes de l'espace de noms System.Collections.Concurrent ou envisagez d'utiliser une collection immuable. Pour plus d’informations, consultez Thread-Safe Collections.

Choisir une collection

En général, vous devez utiliser des collections génériques. Le tableau suivant décrit certains scénarios de collection courants et les classes de collection que vous pouvez utiliser pour ces scénarios. Si vous débutez avec les collections génériques, le tableau suivant vous aidera à choisir la collection générique qui convient le mieux à votre tâche :

Je veux... Options de collection génériques Options de collection non générique Options de collection thread-safe ou immuable
Stocker des éléments en tant que paires clé/valeur pour rechercher rapidement par clé Dictionary<TKey,TValue> Hashtable

(Collection de paires clé/valeur organisées en fonction du code de hachage de la clé.)		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Accéder aux éléments par index List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Utiliser des éléments premier entré, premier sorti (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Utiliser des données dernier entré, premier sorti (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Accéder aux éléments de manière séquentielle LinkedList<T> Aucune recommandation Aucune recommandation
Recevoir des notifications lorsque des éléments sont supprimés ou ajoutés à la collection. (implémente INotifyPropertyChanged et INotifyCollectionChanged) ObservableCollection<T> Aucune recommandation Aucune recommandation
Collection triée SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Ensemble de fonctions mathématiques HashSet<T>

SortedSet<T>		 Aucune recommandation ImmutableHashSet<T>

ImmutableSortedSet<T>

Complexité algorithmique des collections

Lorsque vous choisissez une classe de collection, il vaut la peine d’envisager des compromis potentiels en termes de performances. Utilisez le tableau suivant pour référencer la comparaison des différents types de collections mutables en complexité algorithmique à leurs équivalents immuables correspondants. Souvent, les types de collection immuables sont moins performants, mais offrent une immuabilité, ce qui est souvent un avantage comparatif valide.

Mutable Coût amorti Pire cas Immuable Complexité
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.AddRecherche O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Dictionary<T> Recherche O(1) O(1) – ou strictement O(n) ImmutableDictionary<T> Recherche O(log n)
SortedDictionary<T>.Add O(log n) O(n journal n) ImmutableSortedDictionary<T>.Add O(log n)

Un List<T> peut être énuméré efficacement à l’aide d’une for boucle ou d’une foreach boucle. Toutefois, un ImmutableList<T> effectue un travail médiocre à l'intérieur d'une boucle for, en raison du temps O(log n) requis par son indexeur. Énumérer un ImmutableList<T> à l'aide d'une boucle foreach est efficace, car ImmutableList<T> utilise un arbre binaire pour stocker ses données au lieu d'un tableau, comme List<T>. Un tableau peut être rapidement indexé, tandis qu’une arborescence binaire doit être parcourue jusqu’à ce que le nœud avec l’index souhaité soit trouvé.

En outre, la complexité de SortedSet<T> est identique à celle de ImmutableSortedSet<T> puisqu'ils utilisent tous deux des arborescences binaires. La différence significative est que ImmutableSortedSet<T> utilise une arborescence binaire immuable. Comme ImmutableSortedSet<T> propose également une classe System.Collections.Immutable.ImmutableSortedSet<T>.Builder qui permet une modification, vous pouvez avoir à la fois l'immuabilité et les performances.

Titre Descriptif
Sélection d’une classe de collection Décrit les différentes collections et vous aide à en sélectionner un pour votre scénario.
Types de collection couramment utilisés Décrit les types de collection génériques et non génériques couramment utilisés, tels que System.Array, System.Collections.Generic.List<T>et System.Collections.Generic.Dictionary<TKey,TValue>.
Quand utiliser des collections génériques Décrit l’utilisation des types de collection génériques.
Comparaisons et tris dans les collections Décrit l’utilisation des comparaisons d’égalité et des comparaisons de tri dans les collections.
Types de collection triés Décrit les performances et les caractéristiques des collections triées.
Types de collections Hashtable et Dictionary Décrit les fonctionnalités des types de dictionnaires génériques et non génériques basés sur le hachage.
Collections thread-safe Décrit les types de collection tels que System.Collections.Concurrent.BlockingCollection<T> et System.Collections.Concurrent.ConcurrentBag<T> qui prennent en charge l’accès simultané sécurisé et efficace à partir de plusieurs threads.
System.Collections.Immutable Présente les collections immuables et fournit des liens vers les types de collection.

Référence

  • Last updated on