How C# SortedSet Maintains Ordered Unique Elements

In C#, SortedSet<T> is a generic collection that stores unique elements in a sorted order without requiring manual sorting after insertions. This article explores how SortedSet<T> operates under the hood, how it guarantees both uniqueness and sorting simultaneously via self-balancing binary search trees, and when you should use it over alternatives like HashSet<T> or a sorted List<T>.

What is SortedSet<T>?

SortedSet<T> is part of the System.Collections.Generic namespace and represents a strongly typed collection of objects maintained in ascending order according to an IComparer<T> implementation. Unlike standard lists, it prohibits duplicate values. If an attempt is made to insert an item that already exists in the set, the operation fails silently by returning false without throwing an exception.

The Underlying Data Structure: Red-Black Tree

The ordering and uniqueness guarantees of SortedSet<T> are driven by its underlying data structure: a self-balancing binary search tree known as a Red-Black Tree.

A Red-Black Tree maintains balanced height by adhering to specific coloring and structural rules:

  1. Every node is colored either red or black.
  2. The root node is always black.
  3. Red nodes cannot have red children (no two consecutive red nodes on any path).
  4. Every path from a given node to any of its descendant null references contains the same number of black nodes.

Because of these invariants, the tree remains roughly balanced, ensuring the path from the root to the farthest leaf is no more than twice as long as the path to the nearest leaf.

How It Enforces Uniqueness and Order

Every insertion, search, and removal operation in a SortedSet<T> navigates the Red-Black Tree starting from the root:

  1. Comparison: When you call .Add(item), the collection compares the new item with the current node using either Comparer<T>.Default or a custom IComparer<T> passed to the constructor.
  2. Traversal:
    • If the new item is smaller than the current node (comparison returns < 0), traversal continues to the left child.
    • If the new item is greater (comparison returns > 0), traversal continues to the right child.
    • If the comparison returns 0, the collection treats the item as an identical duplicate. The insertion aborts, and the set remains unchanged.
  3. Rebalancing: Once an item is placed in an open leaf position, the tree performs rotations and node recoloring if any Red-Black Tree properties were violated.
  4. Ordered Retrieval: Enumerating the set executes an in-order traversal (left child, current node, right child), naturally yielding the items in sorted order without requiring an explicit sort phase.

Performance Characteristics

Because operations are bounded by tree height, SortedSet<T> offers predictable performance:

  • Search (Contains): \(O(\log n)\)
  • Insertion (Add): \(O(\log n)\)
  • Deletion (Remove): \(O(\log n)\)
  • Iteration: \(O(n)\)

In contrast, HashSet<T> provides \(O(1)\) constant time complexity for insertions and lookups by using a hash table, but it does not maintain order. A standard List<T> requires an \(O(n \log n)\) sort operation after mutations to keep items in order.

Advanced Set Operations

Beyond individual item manipulation, SortedSet<T> provides built-in set-algebra methods, including:

  • UnionWith: Combines elements from another collection, skipping duplicates.
  • IntersectWith: Modifies the set to contain only elements present in both collections.
  • ExceptWith: Removes all elements in the specified collection from the current set.
  • GetViewBetween: Returns a live sub-set view between lower and upper bounds in \(O(\log n)\) time without copying the data.

Use SortedSet<T> whenever your application requires maintaining continuous sorted order of dynamic, non-duplicate data while performing range queries or set-based arithmetic.