Types de collections triées
La classe System.Collections.SortedList, la classe générique System.Collections.Generic.SortedList<TKey, TValue> et la classe générique System.Collections.Generic.SortedDictionary<TKey, TValue> sont semblables à la classe Hashtable et à la classe générique Dictionary<TKey, TValue> car elles implémentent l'interface IDictionary, mais conservent leurs éléments triés par clé et ne possèdent pas les caractéristiques d'insertion et de récupération O(1) des tables de hachage. Les trois classes possèdent plusieurs fonctionnalités en commun :
Les trois classes implémentent toutes l'interface System.Collections.IDictionary. Les deux classes génériques implémentent également l'interface générique System.Collections.Generic.IDictionary<TKey, TValue>.
Chaque élément est une paire clé/valeur à des fins d'énumération.
.gif "Remarque")
RemarqueLa classe SortedList non générique retourne des objets DictionaryEntry lorsqu'elle est énumérée, même si les deux types génériques retournent des objets KeyValuePair<TKey, TValue>.
Les éléments sont triés selon une implémentation d'System.Collections.IComparer (pour la classe SortedList non générique) ou une implémentation d'System.Collections.Generic.IComparer<T> (pour les deux classes génériques).
Chaque classe fournit des propriétés qui retournent des collections contenant uniquement les clés ou uniquement les valeurs.
Le tableau suivant répertorie certaines des différences entre les deux classes de liste triée et la classe SortedDictionary<TKey, TValue>.
Classe non générique SortedList et classe générique SortedList<TKey, TValue> |
Classe générique SortedDictionary<TKey, TValue> |
|---|---|
Les propriétés qui retournent des clés et des valeurs sont indexées, entraînant ainsi une extraction indexée efficace. |
Aucune extraction indexée. |
L'extraction correspond à O(log n). |
L'extraction correspond à O(log n). |
L'insertion et la suppression correspondent généralement à O(n) ; toutefois, l'insertion correspond à O(1) pour les données qui sont déjà dans l'ordre de tri, afin que chaque élément soit ajouté à la fin de la liste. (Cela suppose qu'il n'est pas nécessaire d'effectuer un redimensionnement.) |
L'insertion et la suppression correspondent à O (log n). |
Requiert moins de mémoire qu'un SortedDictionary<TKey, TValue>. |
Requiert plus de mémoire que la classe non générique SortedList et la classe générique SortedList<TKey, TValue>. |
Pour les listes ou les dictionnaires triés qui doivent être accessibles simultanément à partir de plusieurs threads, vous pouvez ajouter une logique de tri à une classe qui dérive de ConcurrentDictionary<TKey, TValue>.
| Remarque |
|---|
Pour les valeurs qui contiennent leurs propres clés (par exemple, les enregistrements d'employé qui contiennent un numéro d'ID de l'employé), vous pouvez créer une collection à clé qui possède certaines caractéristiques d'une liste et certaines caractéristiques d'un dictionnaire, en dérivant de la classe générique KeyedCollection<TKey, TItem>. |
À partir du .NET Framework version 4, la classe SortedSet<T> fournit une arborescence autonome qui maintient les données triées dans un certain ordre après les insertions, les suppressions et les recherches. Cette classe et la classeHashSet<T> implémentent l'interface ISet<T>.
Voir aussi
Référence
System.Collections.IDictionary
System.Collections.Generic.IDictionary<TKey, TValue>
ConcurrentDictionary<TKey, TValue>