The System.Collections.SortedList class, the System.Collections.Generic.SortedList generic class, and the System.Collections.Generic.SortedDictionary generic class are similar to the System.Collections.Hashtable class and the System.Collections.Generic.Dictionary generic class in that they implement the System.Collections.IDictionary interface, but they maintain their elements in sort order by key, and they do not have the O(1) insertion and retrieval characteristic of hash tables. The three classes have several features in common:
All three classes implement the System.Collections.IDictionary interface. The two generic classes also implement the System.Collections.Generic.IDictionary generic interface.
Each element is a key/value pair for enumeration purposes.
Elements are sorted according to a System.Collections.IComparer implementation (for nongeneric System.Collections.SortedList) or a System.Collections.Generic.IComparer implementation (for the two generic classes).
Each class provides properties that return collections containing only the keys or only the values.
The following table lists some of the differences between the two sorted list classes and the System.Collections.Generic.SortedDictionary class.
| System.Collections.SortedList nongeneric class and System.Collections.Generic.SortedList generic class | System.Collections.Generic.SortedDictionary generic class |
|---|---|
| The properties that return keys and values are indexed, allowing efficient indexed retrieval. | No indexed retrieval. |
Retrieval is O(log n). |
Retrieval is O(log n). |
Insertion and removal are generally O(n); however, insertion is O(log n) for data that are already in sort order, so that each element is added to the end of the list. (This assumes that a resize is not required.) |
Insertion and removal are O(log n). |
| Uses less memory than a System.Collections.Generic.SortedDictionary. | Uses more memory than the System.Collections.SortedList nongeneric class and the System.Collections.Generic.SortedList generic class. |
For sorted lists or dictionaries that must be accessible concurrently from multiple threads, you can add sorting logic to a class that derives from System.Collections.Concurrent.ConcurrentDictionary. When considering immutability, the following corresponding immutable types follow similar sorting semantics: System.Collections.Immutable.ImmutableSortedSet and System.Collections.Immutable.ImmutableSortedDictionary.
The System.Collections.Generic.SortedSet class provides a self-balancing tree that maintains data in sorted order after insertions, deletions, and searches. This class and the System.Collections.Generic.HashSet class implement the System.Collections.Generic.ISet interface.