SortedList and SortedDictionary Collection Types

SortedList and SortedDictionary Col...

Collapse All

This page is specific to

Microsoft Visual Studio 2008/.NET Framework 3.5

Other versions are also available for the following:

.NET Framework Developer's Guide

SortedList and SortedDictionary Collection Types

Updated: November 2007

The System.Collections..::.SortedList class, the System.Collections.Generic..::.SortedList<(Of <(TKey, TValue>)>) generic class, and the System.Collections.Generic..::.SortedDictionary<(Of <(TKey, TValue>)>) generic class are similar to the Hashtable class and the Dictionary<(Of <(TKey, TValue>)>) generic class in that they implement the 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<(Of <(TKey, TValue>)>) generic interface.

Each element is a key/value pair for enumeration purposes.

Note:
The nongeneric SortedList class returns DictionaryEntry objects when enumerated, while the two generic types return KeyValuePair<(Of <(TKey, TValue>)>) objects.

Elements are sorted according to an System.Collections..::.IComparer implementation (for nongeneric SortedList) or an System.Collections.Generic..::.IComparer<(Of <(T>)>) 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 SortedDictionary<(Of <(TKey, TValue>)>) class.

SortedList nongeneric class and SortedList<(Of <(TKey, TValue>)>) generic class	SortedDictionary<(Of <(TKey, TValue>)>) 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(1) 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 SortedDictionary<(Of <(TKey, TValue>)>).	Uses more memory than the SortedList nongeneric class and the SortedList<(Of <(TKey, TValue>)>) generic class.

Note:
For values that contain their own keys (for example, employee records that contain an employee ID number), you can create a keyed collection that has some characteristics of a list and some characteristics of a dictionary by deriving from the KeyedCollection<(Of <(TKey, TItem>)>) generic class.