The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:
-
SortedList uses less memory than SortedDictionary.
-
SortedDictionary has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList.
-
If the list is populated all at once from sorted data, SortedList is faster than SortedDictionary.
Each key/value pair can be retrieved as a KeyValuePair structure, or as a DictionaryEntry through the nongeneric IDictionary interface.
Keys must be immutable as long as they are used as keys in the SortedDictionary. Every key in a SortedDictionary must be unique. A key cannot be a null reference (Nothing in Visual Basic), but a value can be, if the value type TValue is a reference type.
SortedDictionary requires a comparer implementation to perform key comparisons. You can specify an implementation of the IComparer generic interface by using a constructor that accepts a comparer parameter; if you do not specify an implementation, the default generic comparer Comparer.Default is used. If type TKey implements the System.IComparable generic interface, the default comparer uses that implementation.
The foreach statement of the C# language (for each in C++, For Each in Visual Basic) requires the type of each element in the collection. Since each element of the SortedDictionary is a key/value pair, the element type is not the type of the key or the type of the value. Instead, the element type is KeyValuePair. The following code shows C#, C++, and Visual Basic syntax.
foreach (KeyValuePair<int, string> kvp in myDictionary) {...}
for each (KeyValuePair<int, String^> kvp in myDictionary) {...}
For Each kvp As KeyValuePair(Of Integer, String) In myDictionary
...
Next myKVP
The foreach statement is a wrapper around the enumerator, which allows only reading from the collection, not writing to it.