Collections et structures de données

Des données similaires peuvent souvent être gérées plus efficacement quand elles sont stockées et manipulées en tant que collection. Vous pouvez utiliser la classe System.Array ou les classes des espaces de noms System.Collections, System.Collections.Generic, System.Collections.Concurrent et System.Collections.Immutable pour ajouter, supprimer et modifier des éléments ou une plage d'éléments dans une collection.

Il existe deux principaux types de collections : les collections génériques et non génériques. Les collections génériques sont de type sécurisé au moment de la compilation. Pour cette raison, les collections génériques offrent généralement de meilleures performances. Les collections génériques acceptent un paramètre de type lorsqu'elles sont construites, et ne nécessitent pas de transtypage du type Object quand vous ajoutez ou supprimez des éléments de la collection. De plus, la plupart des collections génériques sont prises en charge par 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. Cependant, vous pouvez rencontrer ces collections non génériques dans du code plus ancien.

À compter de .NET Framework 4, 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 de plusieurs threads. Les classes de collection immuable de System.Collections.Immutable l’espace de noms (package NuGet) 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 communes à toutes les collections

Toutes les collections fournissent des méthodes pour l'ajout, la suppression ou la recherche d'éléments au sein d'une collection. De plus, toutes les collections qui implémentent directement ou indirectement l'interface ICollection ou ICollection<T> partagent les fonctionnalités suivantes :

• Possibilité d’énumérer la collection

  Les collections du .NET implémentent soit System.Collections.IEnumerable, soit System.Collections.Generic.IEnumerable<T> pour permettre à la collection d'être parcourue. Un énumérateur peut être vu comme un pointeur mobile pointant vers n'importe quel élément d'une 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 étant un type requêtable et peut être interrogée avec LINQ. Les requêtes LINQ fournissent un modèle commun d'accès aux données. Elles sont généralement plus concises et lisibles que les boucles foreach standard, et fournissent des fonctionnalités de filtrage, de tri 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 d’une collection dans un tableau

  Toutes les collections peuvent être copiées dans un tableau à l'aide de la méthode CopyTo. Toutefois, l'ordre des éléments du nouveau tableau sera basé sur l'ordre où ils sont retournés par l'énumérateur. Le tableau résultant est toujours unidimensionnel avec une limite inférieure de zéro.

De plus, de nombreuses classes de collection comprennent les fonctionnalités suivantes :

• Propriétés Capacity et Count

  La propriété Capacity d'une collection indique le nombre d'éléments qu'elle peut contenir. La propriété Count d'une collection indique le nombre d'éléments qu'elle contient réellement. Certaines collections masquent l'une de ces propriétés, voire les deux.

  La capacité de la plupart des collections s'étend automatiquement quand la valeur de la propriété Capacity est atteinte. La mémoire est réallouée et les éléments sont copiés depuis l'ancienne collection vers la nouvelle. Cela permet de réduire le code nécessaire à l'utilisation de la collection. Toutefois, les performances de la collection peuvent être affectées. Par exemple, pour List<T>, si Count est inférieur à Capacity, l'ajout d'un élément correspond à une opération O(1). Si la capacité doit être augmentée pour intégrer un nouvel élément, l'ajout d'un élément devient une opération O(n), où n est Count. Le meilleur moyen d'éviter la dégradation des performances en raison des réallocations est de définir la propriété Capacity sur la taille estimée de la collection.

  BitArray est un cas particulier. Sa capacité est égale à sa longueur, qui est elle-même égale à son nombre.

• 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 l'espace de noms System.Collections ont une limite inférieure de zéro, ce qui signifie qu'elles sont indexées à 0. Par défaut, Array a une limite inférieure de zéro. Vous pouvez cependant définir une autre limite inférieure quand vous créez une instance de la classe Array avec Array.CreateInstance.

• Synchronisation pour un accès depuis plusieurs threads (classes System.Collections 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 Collections thread-safe.

Choisir une collection

En règle générale, vous devez utiliser des collections génériques. Le tableau suivant décrit certains scénarios courants concernant les collections, ainsi que les classes de collection que vous pouvez utiliser pour ces scénarios. Si vous ne connaissez pas encore les collections génériques, ce tableau vous aidera à choisir la collection générique qui répond le mieux à vos besoins.

Complexité algorithmique des collections

Lors du choix d’une classe de collection, il est utile d’envisager des compromis potentiels en termes de performances. Utilisez le tableau suivant pour comparer la complexité algorithmique des différents types de collections mutables à celle de leurs homologues immuables. Souvent, les types de collections immuables sont moins performants mais offrent l'immuabilité, ce qui est souvent un avantage comparatif valable.

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

En outre, SortedSet<T> a la même complexité que ImmutableSortedSet<T>. C’est parce qu’ils utilisent tous les deux des arborescences binaires. La différence significative, bien sûr, est que ImmutableSortedSet<T> utilise une arborescence binaire immuable. Comme ImmutableSortedSet<T> offre également une classe System.Collections.Immutable.ImmutableSortedSet<T>.Builder qui permet la mutation, vous pouvez avoir à la fois l’immuabilité et les performances.

Rubriques connexes

Référence

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable