Collections et structures de données

  • Article

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 :

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.

Je souhaite : Options de collection générique Options de collection non générique Options de collection thread-safe ou immuable
Stocker les éléments sous forme de paires clé/valeur pour une recherche rapide 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 quand 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

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.

Mutable Coût amorti Pire cas Non modifiable 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>.Add, recherche 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 log n) ImmutableSortedDictionary<T>.Add O(log n)

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.

Titre Description
Sélection d’une classe de collection Décrit les différentes collections et permet d'en sélectionner une pour votre scénario.
Types de collections couramment utilisés Décrit les types de collection génériques et non génériques fréquemment utilisés, tels que System.Array, System.Collections.Generic.List<T> et System.Collections.Generic.Dictionary<TKey,TValue>.
Quand utiliser les collections génériques Traite de l'utilisation des types de collections génériques.
Comparaisons et tris dans les collections Aborde l'utilisation des comparaisons d'égalité et de tri dans les collections.
Types de collections triées Aborde les caractéristiques et les performances des collections triées.
Types de collections Hashtable et Dictionary Décrit les fonctionnalités des types de dictionnaires basés sur le hachage génériques et non génériques.
Collections thread-safe Décrit les types de collections 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 de plusieurs threads.
System.Collections.Immutable Présente les collections immuables et fournit des liens vers les types de collection.

Référence

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