C# Reference ยท Collections
SortedDictionary and SortedList
Reference for C# SortedDictionary<TKey,TValue> and SortedList<TKey,TValue>: key-ordered maps, how they differ, index access, costs and when to use each.
SortedDictionary<TKey,TValue> and SortedList<TKey,TValue> are two maps that keep their entries ordered by key. Enumerating either one yields the pairs in ascending key order, and both look up a key in O(log n), compared with O(1) on average for Dictionary. Use them when you need ordered iteration or ordered range-style processing as well as lookup by key.
They differ in how they store data. SortedDictionary is a balanced tree: inserts and removals are O(log n) and every entry has its own node. SortedList is two parallel arrays, sorted by key: it uses less memory and gives fast index access, but inserting or removing an entry in the middle shifts the arrays, which is O(n).
var map = new SortedDictionary<string, int> { ["pear"] = 3, ["apple"] = 5 }; foreach (var (key, value) in map) Console.WriteLine($"{key}={value}"); // apple first
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.
Syntax
public class SortedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue> where TKey : notnull { public SortedDictionary(); public SortedDictionary(IComparer<TKey>? comparer); public TValue this[TKey key] { get; set; } public void Add(TKey key, TValue value); public bool Remove(TKey key); public bool TryGetValue(TKey key, out TValue value); } public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue> where TKey : notnull { public SortedList(); public SortedList(int capacity); public IList<TKey> Keys { get; } public IList<TValue> Values { get; } public int IndexOfKey(TKey key); public int IndexOfValue(TValue value); public void RemoveAt(int index); public void TrimExcess(); }
| Name | Description |
|---|---|
key |
Unique, non-null key. Order and equality come from the comparer. |
comparer |
Defines the sort order; the default is Comparer<TKey>.Default. |
index |
Zero-based position in the sorted order (SortedList only). |
Returns: TryGetValue and Remove return bool. IndexOfKey returns -1 if the key is missing.
Errors: the indexer getter throws KeyNotFoundException for a missing key; Add throws ArgumentException for a duplicate; null keys throw ArgumentNullException; SortedList.RemoveAt and the Keys/Values indexers throw ArgumentOutOfRangeException for a bad index. Changing the map during enumeration throws InvalidOperationException.
Usage notes
- Which one?
SortedDictionaryis better when entries arrive in random order and the map is large and changes often.SortedListis better for small or read-mostly maps, when data is added in sorted order (appending at the end is cheap), and when you want index access or low memory use. - Complexity: lookup is O(log n) for both. Insert and remove are O(log n) for
SortedDictionaryand O(n) forSortedList(O(1) amortized when appending the largest key). - Plain
Dictionaryis faster for lookups. Pick a sorted map for the ordering, not for speed. SortedDictionaryhas no index and no first/last property.Keys.First()is O(log n) butKeys.Last()through LINQ walks the whole sequence, which is O(n). If you need cheap first/last access, useSortedSet<T>withMinandMax, or aSortedList.- Keys must not change in a way that alters their order after insertion.
- Comparer decides identity. With
StringComparer.OrdinalIgnoreCase,"A"and"a"are the same key. - Sorting by value is not supported. Use
OrderBy(p => p.Value)on the pairs, or keep a second structure. - Old non-generic
SortedListinSystem.Collectionsstoresobject; avoid it. - Not thread-safe for concurrent writes.