How to use SortedSet in C#

This collection uses a tree-based data structure internally to keep elements in order, ensuring efficient insertion with an O(log n) complexity. This is much more performant than repeatedly sorting a list, which has an O(n log n) time complexity.

For example, How to create a SortedSet and add some elements:

using System.Collections.Generic;

var sortedSet = new SortedSet<string>();

sortedSet.Add("Charlie");
PrintOut(sortedSet);

sortedSet.Add("Alice");
PrintOut(sortedSet);

sortedSet.Add("Bob");
PrintOut(sortedSet);

Output:

Charlie
Alice, Charlie
Alice, Bob, Charlie

As you can see, SortedSet maintains elements in sorted order as new items are added.

You can also iterate through the SortedSet with a foreach loop:

foreach (var name in sortedSet)
{
    Console.WriteLine(name);
}

This will output the elements in sorted order:

Alice
Bob
Charlie

Using the Min and Max Properties

When maintaining a sorted collection, often the minimum and maximum values are important. SortedSet provides Min and Max properties to access these:

Console.WriteLine($"Min = {sortedSet.Min}");
Console.WriteLine($"Max = {sortedSet.Max}");

This will output:

Min = Alice
Max = Charlie

Using SortedSet with Custom Classes

To use your own class with SortedSet, implement the IComparable<T> interface in your class. This allows the class to define how objects should be compared for sorting purposes.

Here’s an example using a Person class that compares objects by last name:

public class Person : IComparable<Person>
{
    public string FirstName { get; set; }
    public string LastName { get; set; }

    public int CompareTo(Person other)
    {
        return this.LastName.CompareTo(other.LastName);
    }
}

Now you can use this class in a SortedSet:

var sortedPeople = new SortedSet<Person>();

sortedPeople.Add(new Person() { FirstName = "John", LastName = "Doe" });
sortedPeople.Add(new Person() { FirstName = "Jane", LastName = "Smith" });
sortedPeople.Add(new Person() { FirstName = "Alice", LastName = "Brown" });

foreach (var person in sortedPeople)
{
    Console.WriteLine($"{person.FirstName} {person.LastName}");
}

This will output:

Alice Brown
John Doe
Jane Smith

Sorting by Multiple Properties

If you want to sort by multiple properties, modify the CompareTo method.

For example, if you want to compare people by their last name and then by their first name:

public class Person : IComparable<Person>
{
    public string FirstName { get; set; }
    public string LastName { get; set; }

    public int CompareTo(Person other)
    {
        int lastNameComparison = this.LastName.CompareTo(other.LastName);

        if (lastNameComparison != 0)
            return lastNameComparison;

        return this.FirstName.CompareTo(other.FirstName);
    }
}

Now, if we add people with the same last name but different first names:

var sortedPeople = new SortedSet<Person>();

sortedPeople.Add(new Person() { FirstName = "John", LastName = "Doe" });
sortedPeople.Add(new Person() { FirstName = "Jane", LastName = "Doe" });
sortedPeople.Add(new Person() { FirstName = "Alice", LastName = "Brown" });

foreach (var person in sortedPeople)
{
    Console.WriteLine($"{person.FirstName} {person.LastName}");
}

This will output:

Alice Brown
Jane Doe
John Doe

Changing the Sort Order with IComparer<T>

You can customize the sort order of your elements by implementing your own IComparer<T>.

For instance, if you want to sort the SortedSet of strings in descending order, you can create a custom comparer like this:

public class DescendingComparer : IComparer<string>
{
    public int Compare(string a, string b)
    {
        return b.CompareTo(a); 
    }
}

Now, pass an instance of DescendingComparer to the SortedSet constructor:

var sortedSet = new SortedSet<string>(new DescendingComparer());

sortedSet.Add("Charlie");
sortedSet.Add("Alice");
sortedSet.Add("Bob");

foreach (var name in sortedSet)
{
    Console.WriteLine(name);
}

This will output the names in descending order:

Charlie
Bob
Alice

Allowing Non-Unique Values

By default, SortedSet only allows unique values. If you want to allow duplicates, you can provide a custom comparer that never returns 0 when comparing two equal elements.

For example, let’s say you want to allow non-unique last names for Person objects, but still sort them by last name:

public class Person : IComparable<Person>
{
    public string FirstName { get; set; }
    public string LastName { get; set; }

    public int CompareTo(Person other)
    {
        var compare = this.LastName.CompareTo(other.LastName);

        if (compare == 0)
            return -1; // Allow non-unique by never returning 0

        return compare;
    }
}

Now, when adding duplicate last names:

var sortedPeople = new SortedSet<Person>();

sortedPeople.Add(new Person() { FirstName = "John", LastName = "Doe" });
sortedPeople.Add(new Person() { FirstName = "Jane", LastName = "Doe" });

foreach (var person in sortedPeople)
{
    Console.WriteLine($"{person.FirstName} {person.LastName}");
}

This will output:

Jane Doe
John Doe

Even though both people have the same last name, the SortedSet allows them because the custom comparer never returns 0.