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 similaires à 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 ni de récupération O(1) des tables de hachage. Les trois classes ont 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 utilisée à des fins d’énumération.
Notes
La classe SortedList non générique retourne des objets DictionaryEntry quand 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>.
| SortedList (classe non générique) et SortedList<TKey,TValue> (classe générique) | SortedDictionary<TKey,TValue> (classe générique) |
|---|---|
| Les propriétés qui retournent des clés et des valeurs sont indexées, ce qui permet une récupération indexée efficace. | Aucune récupération indexée. |
La récupération est O(log n). |
La récupération est O(log n). |
L’insertion et la suppression correspondent généralement à O(n). Toutefois, l’insertion correspond à O(log n) pour les données qui se trouvent déjà en ordre de tri, afin que chaque élément soit ajouté à la fin de la liste. (Cela suppose qu’un redimensionnement n’est pas requis.) |
L’insertion et la suppression sont O(log n). |
| Utilise moins de mémoire qu’un SortedDictionary<TKey,TValue>. | Utilise 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>. Lorsque vous envisagez l’immuabilité, les types immuables correspondants suivants suivent une sémantique de tri similaire : ImmutableSortedSet<T> et ImmutableSortedDictionary<TKey,TValue>.
Notes
Pour les valeurs qui contiennent leurs propres clés (par exemple, des enregistrements d’employés 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 de .NET Framework 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 classe HashSet<T> implémentent l’interface ISet<T>.
