Skip to content
Tutorials Center
My learning

Topics

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).

C#
var map = new SortedDictionary<string, int> { ["pear"] = 3, ["apple"] = 5 };
foreach (var (key, value) in map) Console.WriteLine($"{key}={value}");  // apple first

Try it

C# Keys always come out sorted

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.

C# SortedList and index access

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

C#
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? SortedDictionary is better when entries arrive in random order and the map is large and changes often. SortedList is 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 SortedDictionary and O(n) for SortedList (O(1) amortized when appending the largest key).
  • Plain Dictionary is faster for lookups. Pick a sorted map for the ordering, not for speed.
  • SortedDictionary has no index and no first/last property. Keys.First() is O(log n) but Keys.Last() through LINQ walks the whole sequence, which is O(n). If you need cheap first/last access, use SortedSet<T> with Min and Max, or a SortedList.
  • 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 SortedList in System.Collections stores object; avoid it.
  • Not thread-safe for concurrent writes.