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.
var set = new SortedSet<int> { 5, 1, 3, 1 }; Console.WriteLine(string.Join(",", set)); // 1,3,5
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 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
GetViewBetweenchanges when the original changes. ItsCountcan 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]. UseElementAtfrom LINQ (O(n)) or keep aList<T>if you need positions. MinandMaxwalk 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.