Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

C# SortedSet Usage: Ordered Set in .NET

Learn how to use C# SortedSet<T> for ordered, unique collections: creation, operations, custom comparers, and performance tradeoffs.

~6 min readC#
#SortedSet#C# Collections#.NET#Data Structures
Illustration of a C# SortedSet maintaining unique elements in ascending order with a custom comparer.

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 SortedSet<T> 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. By default it uses the IComparer<T> returned by Comparer<T>.Default, so numeric types are ordered ascending and strings use the current culture's comparison rules. The .NET implementation uses a balanced binary search tree (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 maintains its balancing invariant 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:

csharp
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); } // Prints: // 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>:

csharp
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:

csharp
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:

csharp
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:

csharp
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}"); } // Prints: // 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.

CollectionOrderingLookup ComplexityUse Case
HashSet<T>NoneO(1) averageFast membership checks without order
SortedSet<T>SortedO(log n)Unique elements that need to be enumerated in order
SortedDictionary<TKey, TValue>Sorted by keyO(log n)Key-value pairs with ordered iteration

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, so you cannot access the nth element directly. Min and Max give you the smallest and largest elements without enumerating the set; like other tree operations, retrieving them is O(log n). 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 mutable 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:

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

Try matching browser tools

All tools

Small utilities that fit C# work — they run entirely in this browser tab, so nothing you paste leaves your device.

All C# guides

More in C#

All C# guides

The guides filed next to this one in C#, in library order.