Mastering SortedSet in C#

Key Features:

• Unique Elements: SortedSet<T> automatically ignores duplicate elements. Each item in the set is unique.
• Sorted Order: Elements are always sorted (ascending by default or custom via an IComparer<T>).
• Implements ISet<T>: Supports standard set operations like Union, Intersection and Difference.
• Efficient Performance : Operations such as Add, Remove and Contains typically run in O(log n) time.
• Balanced Tree Structure : Internally implemented using a self-balancing binary search tree (like a red-black tree) for efficient lookups and ordering.
• Best Use Case: Use SortedSet<T> when you need to store unique elements while keeping them sorted automatically.
• Supports Custom Objects: You can store user-defined types, provided you implement proper comparison logic (e.g., by implementing IComparable<T> or providing a custom comparer).
• Not Thread-Safe: SortedSet is not synchronized for multi-threaded access. Use locking or a thread-safe wrapper when working in concurrent environments.

Step-by-Step Visualization Example of SortedSet Internal Storage

Here’s a detailed, step-by-step walkthrough showing how SortedSet<T> in C#, internally manages the insertion sequence (40, 30, 60, 50, 10, 70, 20) and then performs Remove(20).

1. When You Need Unique and Sorted Elements

If your use case requires both uniqueness and sorted order, SortedSet<T> is the perfect fit. Unlike List<T>, it prevents duplicates and unlike HashSet<T>, it automatically maintains ascending order.

• Maintaining a sorted list of usernames or IDs without duplicates
• Ranking systems where order must always be maintained.
• Keeping sorted logs or timestamps for efficient range queries.

2. When You Perform Frequent Set Operations

SortedSet<T> implements the ISet<T> interface, offering efficient set-based operations like : UnionWith(), IntersectWith(), ExceptWith(), SymmetricExceptWith(). These operations are optimized for sorted data and are faster than manually handling lists or arrays.

3. When You Need Predictable and Ordered Iteration

Elements in a SortedSet<T> are always in sorted order, so iterating over them yields results in sequence. You can also use custom comparers to define your own sort logic such as sorting by name length, descending order or complex object properties.

4. When Consistency and Integrity Matter

Since duplicates are automatically ignored, SortedSet<T> helps ensure data integrity. It’s a great choice for scenarios where duplicates could cause logical errors such as maintaining a list of active sessions, connected users or registered product IDs.

1. When Ordering Is not Needed

If you only need unique elements and don’t care about sorting, HashSet<T> is more efficient. It provides O(1) average-time insertions and lookups, compared to O(log n) in SortedSet<T>.

2. When You Need Index-Based Access

SortedSet<T> does not support random access or indexing (like mySet[3]). If you need to access elements by position or index frequently, use List<T>, Array or SortedList<TKey, TValue>.

3. When Dealing with Heavy Duplicate or Bulk Inserts

If your data involves massive insertions or many duplicates, SortedSet<T> may become slower. Each insertion involves tree balancing and duplicate checks, which can impact performance compared to HashSet<T> or List<T>.

Better approach : Insert all elements into a List<T> or HashSet<T> first and only later convert to a SortedSet<T> if sorting is needed.

4. When Multi-Threading Without Synchronization

SortedSet<T> is not thread-safe. If multiple threads modify it simultaneously, you must use locking or wrap it with ConcurrentBag<T>, ConcurrentDictionary<TKey,TValue> or custom synchronization.

1. Default Constructor

public SortedSet<T>();

Creates an empty SortedSet<T> that uses the default comparer (Comparer<T>.Default). By default, the elements are sorted in ascending order based on the natural ordering of the type T (e.g., numbers -> smallest to largest, strings -> alphabetical order).

SortedSet<int> numbers = new SortedSet<int>();

2. Constructor with Custom Comparer

public SortedSet<T>(IComparer<T>? comparer);

Creates an empty SortedSet<T> but lets you define your own sorting logic through an IComparer<T> implementation. This is helpful when you need custom sorting for example, descending order, case-insensitive sorting or domain-specific comparison.

SortedSet<int> descendingNumbers = new SortedSet<int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
descendingNumbers.Add(10);
descendingNumbers.Add(40);
descendingNumbers.Add(20);

foreach (int num in descendingNumbers)
    Console.WriteLine(num);

// -------- Output ----------
40
20
10

3. Constructor with Collection

public SortedSet<T>(IEnumerable<T> collection);

Creates a SortedSet<T> and initializes it with elements from an existing collection (like a list or array). All duplicates are automatically removed and the elements are sorted as per the default comparer.

List<int> list = new List<int> { 50, 10, 30, 10, 40 };

SortedSet<int> sorted = new SortedSet<int>(list);

foreach (int num in sorted)
    Console.WriteLine(num);

// ------------ Output --------------
10
30
40
50

4. Constructor with Collection and Comparer

public SortedSet<T>(IEnumerable<T> collection, IComparer<T>? comparer);

Combines both - initializes the SortedSet<T> from an existing collection and lets you specify a custom comparer for sorting. Perfect when you have existing data and want to enforce a custom ordering rule.

List<int> list = new List<int> { 40, 10, 30, 60, 20 };

SortedSet<int> descendingSet = new SortedSet<int>(list, Comparer<int>.Create((a, b) => b.CompareTo(a)));

foreach (int num in descendingSet)
    Console.WriteLine(num);

// ------------ Output -------------
60
40
30
20
10

1. Using collection initializer

Creates a SortedSet<string> and populates it with initial values all at once. Ideal when you already know the elements upfront and want concise code.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var set = new SortedSet<string>() { "C#", "Java", "C++", "Python", "React" };
        foreach (var lang in set) {
            Console.WriteLine(lang);
        }
    }
}

C#
C++
Java
Python
React

2. Using Add() method

Starts with an empty SortedSet<string> and adds elements one by one using Add(). Useful when elements arrive dynamically or you need to check the add-result (duplicate detection).

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var set = new SortedSet<string>();
        set.Add("Python");
        set.Add("Java");
        set.Add("C#");
        set.Add("React");
        set.Add("C++");
        foreach (var lang in set) {
            Console.WriteLine(lang);
        }
    }
}

C#
C++
Java
Python
React