The SortedList`2 generic class is an array of key/value pairs with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary`2 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`2 uses less memory than SortedDictionary`2.

• SortedDictionary`2 has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList`2.

• If the list is populated all at once from sorted data, SortedList`2 is faster than SortedDictionary`2.

Another difference between the SortedDictionary`2 and SortedList`2 classes is that SortedList`2 supports efficient indexed retrieval of keys and values through the collections returned by the SortedList`2.Keys and SortedList`2.Values properties. It is not necessary to regenerate the lists when the properties are accessed, because the lists are just wrappers for the internal arrays of keys and values. The following code shows the use of the SortedList`2.Values property for indexed retrieval of values from a sorted list of strings:

code reference: Generic.SortedList#11

SortedList`2 is implemented as an array of key/value pairs, sorted by the key. Each element can be retrieved as a KeyValuePair`2 object.

Key objects must be immutable as long as they are used as keys in the SortedList`2. Every key in a SortedList`2 must be unique. A key cannot be null, but a value can be, if the type of values in the list, TValue, is a reference type.

SortedList`2 requires a comparer implementation to sort and to perform comparisons. The default comparer Comparer`1.Default checks whether the key type TKey implements IComparable`1 and uses that implementation, if available. If not, Comparer`1.Default checks whether the key type TKey implements IComparable. If the key type TKey does not implement either interface, you can specify a IComparer`1 implementation in a constructor overload that accepts a comparer parameter.

The capacity of a SortedList`2 is the number of elements the SortedList`2 can hold. As elements are added to a SortedList`2, the capacity is automatically increased as required by reallocating the internal array. The capacity can be decreased by calling SortedList`2.TrimExcess or by setting the SortedList`2.Capacity property explicitly. Decreasing the capacity reallocates memory and copies all the elements in the SortedList`2.

For very large SortedList`2 objects, you can increase the maximum capacity to 2 billion elements on a 64-bit system by setting the enabled attribute of the gcAllowVeryLargeObjects configuration element to true in the run-time environment.

The foreach statement of the C# language (for each in C++, For Each in Visual Basic) requires the type of the elements in the collection. Since the elements of the SortedList`2 are key/value pairs, the element type is not the type of the key or the type of the value. Instead, the element type is KeyValuePair`2. For example:

code reference: Generic.SortedList#12

The foreach statement is a wrapper around the enumerator, which only allows reading from, not writing to, the collection.