C# SortedSet Usage: Ordered Set in .NET

When you need to keep a collection of unique elements in a specific order, the C# SortedSet<T> class is a direct answer. It combines the uniqueness guarantee of a HashSet with the sorting behavior of a sorted list, giving you a set that always iterates in sorted order. This article covers practical c# sortedset usage: how to create one, what operations it supports, how to control ordering with a comparer, and where it fits relative to other collection types.

What Is SortedSet and How Does It Keep Order?

SortedSet<T> is a generic collection in the System.Collections.Generic namespace. It stores distinct elements and maintains them in sorted order. The default ordering uses the IComparer<T> implementation for the type T. For numeric types, that means ascending numeric order; for strings, it means lexicographic order based on the current culture. The internal implementation is a balanced binary search tree, typically a red-black tree, which gives O(log n) complexity for insert, delete, and lookup operations.

The sorted order is not a side effect of the collection; it is a core invariant. Every time you add an element, the tree rebalances to preserve the ordering. This means enumeration always yields elements from smallest to largest (or according to the comparer), without requiring a separate sort step.

Creating and Populating a SortedSet

You can instantiate a SortedSet<T> with its parameterless constructor, or you can pass an existing collection to copy from. The following example creates a set of integers and adds a few values, including duplicates:

var numbers = new SortedSet<int>();
numbers.Add(5);
numbers.Add(1);
numbers.Add(3);
numbers.Add(1); // duplicate, ignored

foreach (var n in numbers)
{
    Console.WriteLine(n);
}
// Output: 1, 3, 5

The duplicate 1 is silently ignored because a set cannot contain duplicates. The iteration order is sorted, so you get 1, 3, 5 without any explicit sorting. This is useful when you need to maintain a unique collection that is always ready to display or process in order.

You can also initialize a SortedSet from a collection, such as an array or a List<T>:

var names = new SortedSet<string>(new[] { "banana", "apple", "cherry" });

This copies the elements and immediately sorts them. If the source collection contains duplicates, only one instance of each value is kept.

Common Operations: Add, Remove, Contains, and Set Operations

SortedSet<T> provides the usual set operations you expect from a collection that implements ISet<T>. The Add method returns true if the element was added and false if it was already present. Remove returns true if an element was found and removed. Contains checks for existence in O(log n) time.

Beyond basic operations, SortedSet<T> supports set algebra methods that modify the set in place:

• UnionWith(other) adds all elements from other that are not already present.
• IntersectWith(other) keeps only elements that also exist in other.
• ExceptWith(other) removes all elements that appear in other.
• SymmetricExceptWith(other) keeps elements that are in either set but not in both.

These methods are particularly useful when you need to combine or compare ordered sets. For example, to find common elements between two sorted sets:

var setA = new SortedSet<int> { 1, 2, 3, 4 };
var setB = new SortedSet<int> { 3, 4, 5, 6 };
setA.IntersectWith(setB);
// setA now contains 3, 4

Note that these operations are performed in place. If you need to preserve the original sets, create a copy first.

Using a Custom Comparer for Non-Default Ordering

The default ordering works for types that implement IComparable<T>. For custom classes or when you need a different sort order, you can supply an IComparer<T> to the constructor. This is a common requirement when you want to sort by a specific property or in descending order.

Consider a Person class with Name and Age properties. To sort people by age ascending, you can define a comparer:

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

public class AgeComparer : IComparer<Person>
{
    public int Compare(Person x, Person y)
    {
        return x.Age.CompareTo(y.Age);
    }
}

Then create a SortedSet<Person> using that comparer:

var people = new SortedSet<Person>(new AgeComparer());
people.Add(new Person { Name = "Alice", Age = 30 });
people.Add(new Person { Name = "Bob", Age = 25 });
people.Add(new Person { Name = "Charlie", Age = 35 });

foreach (var p in people)
{
    Console.WriteLine($"{p.Name}: {p.Age}");
}
// Output: Bob: 25, Alice: 30, Charlie: 35

Be careful: the comparer also defines uniqueness. Two Person instances with the same age are considered equal, so adding a second person with age 30 would be rejected even if the name differs. If you need to distinguish people with the same age, the comparer must include a secondary sort key, such as name.

SortedSet vs HashSet vs SortedDictionary

Choosing the right collection depends on what you need. HashSet<T> provides O(1) average lookups but no ordering. SortedSet<T> gives O(log n) operations and sorted iteration. SortedDictionary<TKey, TValue> is for key-value pairs, not just unique values.

If you only need to check for existence and never care about iteration order, HashSet<T> is faster and uses less memory. If you need to repeatedly retrieve the smallest or largest element, or iterate in order, SortedSet<T> is the right choice. SortedDictionary is essentially a SortedSet of key-value pairs, but it does not enforce uniqueness on the value.

Performance and Memory Characteristics

The internal red-black tree structure gives SortedSet<T> predictable logarithmic behavior for add, remove, and lookup. This is slower than HashSet's average constant-time operations, but the tradeoff is the maintained order. For small collections (fewer than a few hundred elements), the difference is negligible. For large collections, the O(log n) factor becomes significant.

Memory usage is higher than a HashSet because each node in the tree stores references to child nodes and a color flag. However, the overhead is still moderate and generally acceptable for most applications. If memory is a primary concern and order is not required, prefer HashSet<T>.

One practical consideration is that SortedSet<T> does not have an indexer. You cannot access the nth element directly. To get the minimum or maximum, you can use the Min and Max properties, which return the smallest and largest elements in O(1) time. If you need to remove the smallest element, call Remove(set.Min).

Thread Safety and Concurrency Considerations

SortedSet<T> is not thread-safe for concurrent reads and writes. If multiple threads modify the same instance, you must synchronize access with a lock or use a concurrent collection. The .NET base class library does not provide a thread-safe sorted set directly. For read-heavy scenarios, you can copy the set to an array and use that for reads, but that is only safe if no writes occur during the copy.

A common pattern is to use a lock object around all operations:

private readonly object _lock = new object();
private SortedSet<int> _set = new SortedSet<int>();

public void Add(int value)
{
    lock (_lock)
    {
        _set.Add(value);
    }
}

For scenarios where you need concurrent reads and occasional writes, consider using an immutable sorted set from a library like System.Collections.Immutable, which provides thread-safe snapshots. The ImmutableSortedSet<T> class offers similar functionality with persistent data structures, but it has a different performance profile.

Common Pitfalls and Edge Cases

One subtle issue arises when the comparer is inconsistent with Equals. The SortedSet uses the comparer for both ordering and equality. If two elements compare as equal but are not considered equal by Equals, you may get unexpected behavior. Always ensure the comparer is consistent with the type's equality semantics.

Another edge case is using a mutable type as the set element. If you modify an object after it has been added, the tree's ordering invariant can break. For example, if a Person object's Age changes after insertion, the set may no longer be sorted correctly. To avoid this, use immutable types or remove and re-add the element when a property changes.

Finally, SortedSet<T> does not allow null for value types, but it does allow null for reference types if the comparer supports it. The default comparer for strings handles null by placing it before other strings. If you use a custom comparer, make sure it handles null explicitly to avoid NullReferenceException.

When you need to iterate over a SortedSet in reverse order, you can use LINQ's Reverse() method, but this creates a new sequence. If reverse iteration is a frequent operation, consider storing the set in a List and reversing that, or use a custom comparer that sorts descending from the start.