C# – How to use SortedSet

by

When you have a collection of elements that you’re continuing to add to, and need to keep the objects in sorted order at all times, you can use SortedSet. Internally, it uses a tree data structure to keep elements in sorted order (O(log n) insertion). This is far more efficient than repeatedly sorting a list (O(n log n) sort).

First, here’s an example of creating a SortedSet and adding multiple elements:

using System.Collections.Generic;

var sortedSet = new SortedSet<int>();

sortedSet.Add(3);
PrintOut(sortedSet);

sortedSet.Add(1);
PrintOut(sortedSet);

sortedSet.Add(2);
PrintOut(sortedSet);
Code language: C# (cs)

This outputs the following, showing that it keeps the elements in sorted order at all times:

3
1,3
1,2,3Code language: plaintext (plaintext)

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

foreach (var i in sortedSet)
{
    Console.WriteLine(i);
}Code language: PHP (php)

This outputs the elements in sorted order:

1
2
3Code language: plaintext (plaintext)

Typically when you have the requirement to keep elements in sorted order, then the min/max values have special meaning for you. SortedSet has Min and Max properties specifically for this purpose. Here’s an example of using these:

Console.WriteLine($"Min = {sortedSet.Min}");
Console.WriteLine($"Max = {sortedSet.Max}");
Code language: C# (cs)

This outputs:

Min = 1
Max = 3

Using SortedSet with your own class

To use your own class with SortedSet, implement IComparable<T> in your class.

Sorting by one property

Here’s an example of implementing IComparable<Movie> on the Movie class, so that it compares movies by their title:

public class Movie : IComparable<Movie>
{
    public string Title { get; set; }
    public int Year { get; set; }

    public int CompareTo(Movie other)
    {
        return this.Title.CompareTo(other.Title);
    }
}
Code language: C# (cs)

Hint: Use the property’s CompareTo() to do the work for you.

Now this can be used with SortedSet:

var sortedMovies = new SortedSet<Movie>();

sortedMovies.Add(new Movie() { Title = "The Matrix", Year = 1999 });
sortedMovies.Add(new Movie() { Title = "The Avengers", Year = 2012 });
sortedMovies.Add(new Movie() { Title = "Jurassic Park", Year = 1993 });

foreach(var movie in sortedMovies)
{
    Console.WriteLine($"{movie.Title}");
}
Code language: C# (cs)

This outputs the following, outputting the movies in sorted order based on their titles:

Jurassic Park
The Avengers
The MatrixCode language: plaintext (plaintext)

Sorting by multiple properties

To make SortedSet sort by multiple properties, compare all of the properties in the CompareTo() method. Here’s an example of comparing movie titles and years:

public class Movie : IComparable<Movie>
{
    public string Title { get; set; }
    public int Year { get; set; }

    public int CompareTo(Movie other)
    {
        var titleCompare = this.Title.CompareTo(other.Title);

        if (titleCompare != 0) //title's aren't equal
            return titleCompare;

        return this.Year.CompareTo(other.Year);
    }
}
Code language: C# (cs)

Now use it with SortedSet:

var sortedMovies = new SortedSet<Movie>();

sortedMovies.Add(new Movie() { Title = "The Avengers", Year = 2012 });
sortedMovies.Add(new Movie() { Title = "Jurassic Park", Year = 1993 });
sortedMovies.Add(new Movie() { Title = "The Avengers", Year = 1998 });

foreach (var movie in sortedMovies)
{
    Console.WriteLine($"{movie.Title} {movie.Year}");
}
Code language: C# (cs)

This outputs the movies sorted by title, then year:

Jurassic Park 1993
The Avengers 1998
The Avengers 2012Code language: plaintext (plaintext)

Because there’s two movies with the same title (The Avengers), it used the year as a tie-breaker (and 1998 < 2012, so the 1998 version comes first).

Changing sort order with IComparer<T>

When using SortedSet, you can change the sort order for any type by creating a class that implements IComparer<T>. For example, let’s say you want to sort integers in descending order:

public class IntsDescending : IComparer<int>
{
    public int Compare(int a, int b)
    {
        return b.CompareTo(a); 
    }
}
Code language: C# (cs)

Now pass in an instance of this IComparer class to the SortedSet constructor:

var sortedSet = new SortedSet<int>(new IntsDescending());

sortedSet.Add(3);
sortedSet.Add(1);
sortedSet.Add(2);

foreach (var i in sortedSet)
{
    Console.WriteLine(i);
}
Code language: C# (cs)

This outputs the integers in descending order:

3
2
1Code language: plaintext (plaintext)

Note: You can add an IComparer<T> for your own class too. This is a good idea if you want to add a non-default comparison, or just don’t want to modify the class.

Allow non-unique values

SortedSet only allows unique values by default. It checks for uniqueness when you insert an element by using the type’s comparer method. If it returns 0, then the value is non-unique and it doesn’t insert it. Therefore, you can have SortedSet accept non-unique values by providing a comparer method that never returns 0.

This breaks the Remove() method (because it can’t find an object for which the comparer method returns 0, hence it can’t remove it). Therefore, alternatively consider adding a tie-breaker property instead (ex: sort movies by title and year, instead of just title).

With that said, I’ll now show an example of how to make SortedSet allow non-unique values. Let’s say you want to sort by movie title, and want to accept movies with non-unique titles. Implement the comparer method so that if two movies have the same title, it doesn’t return a 0 (therefore allowing non-unique titles).

public class Movie : IComparable<Movie>
{
    public string Title { get; set; }
    public int Year { get; set; }

    public int CompareTo(Movie other)
    {
        var compare = this.Title.CompareTo(other.Title);

        if (compare == 0)
            return -1; //to allow non-unique values, don't return 0

        return compare;
    }
}
Code language: C# (cs)

Let’s see this in action by passing in movies with the same title:

var sortedMovies = new SortedSet<Movie>();

sortedMovies.Add(new Movie() { Title = "The Avengers", Year = 1998 });
sortedMovies.Add(new Movie() { Title = "The Avengers", Year = 2012 });

foreach (var movie in sortedMovies)
{
    Console.WriteLine($"{movie.Title} {movie.Year}");
}
Code language: C# (cs)

This outputs the following, showing that the set contains both Movie objects with non-unique titles:

The Avengers 2012
The Avengers 1998Code language: plaintext (plaintext)

Related Articles