SortedSet<T> is one of those .NET collections that looks simple at first: it keeps elements sorted, and it does not allow duplicates.
The interesting part is that both behaviors are controlled by the same comparison logic.
When you provide a custom comparer to a SortedSet<T>, that comparer is not used only to decide the order of the items. It is also used to decide whether two items are the same item for the purpose of the set.
That detail is easy to miss, and it can lead to a surprising bug: Add() returns false even if the object you are adding is a different instance.
The problem
Consider a Patch class:
public sealed record Patch(int Start, int Length);
Suppose we want to keep patches sorted by length, with the longest patch first. A first implementation of the comparer could look like this:
public sealed class PatchLengthComparer : Comparer<Patch>
{
public override int Compare(Patch? x, Patch? y)
{
if (ReferenceEquals(x, y))
return 0;
if (x is null)
return -1;
if (y is null)
return 1;
return y.Length.CompareTo(x.Length);
}
}
At first sight this looks correct. It sorts by Length in descending order.
The problem appears when two different patches have the same length:
var patches = new SortedSet<Patch>(new PatchLengthComparer());
Console.WriteLine(patches.Add(new Patch(Start: 10, Length: 5))); // true
Console.WriteLine(patches.Add(new Patch(Start: 20, Length: 5))); // false
The second patch is not added.
Why?
Because the comparer returns 0 when the two patches have the same length. For a SortedSet<T>, 0 does not mean “these two items have the same sort key”. It means “these two items are equivalent, so only one of them can be in the set”.
The comparer defines both order and uniqueness
A comparer used by SortedSet<T> has two responsibilities:
- It defines the order of the elements.
- It defines when two elements are considered duplicates.
This is the key rule:
Compare(x, y) == 0
means that x and y occupy the same position in the set.
If you compare only by Length, then all patches with the same length are equivalent. That is fine if this is the behavior you want. It is a bug if you want to keep multiple patches with the same length.
The correct approach: add a tie-breaker
To sort by length while still allowing different patches with the same length, the comparer must include another field that differentiates them.
For example, if two patches with the same Length cannot have the same Start, we can use Start as a tie-breaker:
public sealed class PatchLengthComparer : Comparer<Patch>
{
public override int Compare(Patch? x, Patch? y)
{
if (ReferenceEquals(x, y))
return 0;
if (x is null)
return -1;
if (y is null)
return 1;
// Longest patch first.
int byLength = y.Length.CompareTo(x.Length);
if (byLength != 0)
return byLength;
// Tie-breaker: patches with the same length are ordered by start position.
return x.Start.CompareTo(y.Start);
}
}
Now the set can contain more than one patch with the same length:
var patches = new SortedSet<Patch>(new PatchLengthComparer());
Console.WriteLine(patches.Add(new Patch(Start: 10, Length: 5))); // true
Console.WriteLine(patches.Add(new Patch(Start: 20, Length: 5))); // true
Console.WriteLine(patches.Add(new Patch(Start: 10, Length: 5))); // false
The first two patches are different because they have different Start values. The third one is considered a duplicate because both Length and Start match an existing item.
Why not subtract integer values?
You may see comparers written like this:
return y.Length - x.Length;
or:
return y.Start - x.Start;
This is compact, but it is usually better to avoid it.
Use CompareTo() instead:
return y.Length.CompareTo(x.Length);
The reason is simple: subtraction can overflow for large integer values. CompareTo() expresses the intent more clearly and avoids that problem.
For example, prefer this:
int byLength = y.Length.CompareTo(x.Length);
if (byLength != 0)
return byLength;
return x.Start.CompareTo(y.Start);
instead of this:
if (y.Length == x.Length)
return x.Start - y.Start;
return y.Length - x.Length;
The result is a little more verbose, but it is safer and easier to read.
A complete example
Here is a complete runnable example:
using System;
using System.Collections.Generic;
public sealed record Patch(int Start, int Length);
public sealed class PatchLengthComparer : Comparer<Patch>
{
public override int Compare(Patch? x, Patch? y)
{
if (ReferenceEquals(x, y))
return 0;
if (x is null)
return -1;
if (y is null)
return 1;
int byLength = y.Length.CompareTo(x.Length);
if (byLength != 0)
return byLength;
return x.Start.CompareTo(y.Start);
}
}
public static class Program
{
public static void Main()
{
var patches = new SortedSet<Patch>(new PatchLengthComparer());
patches.Add(new Patch(Start: 10, Length: 5));
patches.Add(new Patch(Start: 20, Length: 5));
patches.Add(new Patch(Start: 30, Length: 8));
patches.Add(new Patch(Start: 40, Length: 3));
foreach (var patch in patches)
{
Console.WriteLine($"Start: {patch.Start}, Length: {patch.Length}");
}
}
}
Output:
Start: 30, Length: 8
Start: 10, Length: 5
Start: 20, Length: 5
Start: 40, Length: 3
The patches are sorted by descending length. Patches with the same length are then sorted by their starting position.
The comparer must define a stable total order
A comparer used by SortedSet<T> should be stable and consistent.
That means:
- if
Compare(x, y)returns0, the set will treatxandyas the same element; - if
Compare(x, y)says thatxcomes beforey, thenCompare(y, x)must say the opposite; - the comparison should not depend on random values, current time, external state, or mutable data that can change while the item is inside the set;
- the fields used by the comparer should preferably be immutable.
The last point is important. If you insert an object into a SortedSet<T> and then change one of the properties used by the comparer, the internal order of the set may no longer match the object values.
For example, this is dangerous:
public sealed class Patch
{
public int Start { get; set; }
public int Length { get; set; }
}
If Length or Start is changed after the object has been inserted, the SortedSet<T> will not automatically move the item to the correct position.
A safer design is to make the values immutable:
public sealed record Patch(int Start, int Length);
Or remove the item, change it, and add it again.
When SortedSet is the right collection
SortedSet<T> is a good choice when you need a collection that is:
- always sorted;
- unique according to its comparer;
- efficient for repeated insertions, removals, and lookups.
It is not the best choice when you only need to sort a sequence once. In that case, OrderBy() and ThenBy() are usually simpler:
var sorted = patches
.OrderByDescending(patch => patch.Length)
.ThenBy(patch => patch.Start)
.ToList();
It is also not the best choice if you want to allow multiple elements with exactly the same sort key and no natural tie-breaker. In that case, consider a structure such as:
SortedDictionary<int, List<Patch>>
or use PriorityQueue<TElement, TPriority> if you need priority-based processing rather than set semantics.
A practical checklist
When writing a comparer for SortedSet<T>, ask these questions:
- What is the primary sort key?
- Can two different objects have the same primary sort key?
- If yes, what tie-breaker should be used?
- Should two objects with the same values really be considered duplicates?
- Are all compared fields immutable while the object is inside the set?
The most important rule is this:
return 0;
only when the two objects should be considered the same element in the set.
Conclusion
A custom comparer for SortedSet<T> is not just a sorting function. It defines the identity of the elements inside the set.
If the comparer compares only one property, then all objects with the same value for that property are considered duplicates. To keep multiple objects with the same primary sort key, add one or more tie-breakers until the comparer defines the uniqueness you actually want.
For the Patch example, sorting by Length is not enough. Sorting by Length and then by Start gives the set both a useful order and a correct definition of uniqueness.
