Skip to content
Tutorials Center
My learning

Topics

C# Reference ยท Collections

The SortedSet<T> class

Reference for C# SortedSet<T>: sorted unique items, Min and Max, GetViewBetween range queries, Reverse, custom comparers and O(log n) costs.

SortedSet<T> keeps unique items in sorted order at all times. Internally it is a self-balancing binary search tree (a red-black tree), so adding, removing and looking up an item each cost O(log n), and enumeration always produces the items in ascending order.

Choose it over HashSet<T> when you need ordered iteration, the smallest or largest item, or range queries such as "everything between 10 and 20". Choose HashSet<T> when you only need fast membership tests.

C#
var set = new SortedSet<int> { 5, 1, 3, 1 };
Console.WriteLine(string.Join(",", set));   // 1,3,5

Try it

C# Order, Min, Max and ranges

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# Custom ordering

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 SortedSet<T> : ISet<T>, IReadOnlySet<T>
{
    public SortedSet();
    public SortedSet(IComparer<T>? comparer);
    public SortedSet(IEnumerable<T> collection);

    public T? Min { get; }
    public T? Max { get; }
    public IComparer<T> Comparer { get; }

    public bool Add(T item);
    public bool Remove(T item);
    public bool Contains(T item);
    public SortedSet<T> GetViewBetween(T lowerValue, T upperValue);
    public IEnumerable<T> Reverse();
    public bool TryGetValue(T equalValue, out T actualValue);
}
Name Description
comparer The ordering, which also defines equality: two items are "the same" when the comparer returns 0.
lowerValue, upperValue Inclusive bounds of the view.
equalValue A probe that compares equal to the stored item.

Returns: Min and Max return the smallest and largest item, or default(T) when the set is empty. GetViewBetween returns a live view of the range. Add and Remove return bool.

Errors: GetViewBetween throws ArgumentException if lowerValue is greater than upperValue. Modifying the set while enumerating it throws InvalidOperationException. If T cannot be compared and no comparer is given, operations throw InvalidOperationException. Adding a value outside a view's range through the view throws ArgumentOutOfRangeException.

Usage notes

  • Everything is O(log n) except Count (O(1)) and full enumeration (O(n)). Hash sets are faster for plain membership, roughly O(1).
  • The comparer is the identity. With a case-insensitive comparer, "A" and "a" are one item.
  • Views are live and bounded. A view from GetViewBetween changes when the original changes. Its Count can be O(n) rather than O(1) in some versions, so avoid calling it in a tight loop.
  • No index access. There is no set[3]. Use ElementAt from LINQ (O(n)) or keep a List<T> if you need positions.
  • Min and Max walk the tree rather than reading a stored value, but still cost only O(log n).
  • Stable sort key: items must not change in a way that alters their order after insertion.
  • Priority needs? For repeatedly taking the smallest item with duplicates allowed, PriorityQueue<TElement,TPriority> is lighter.
  • Not thread-safe for concurrent writes.