C# SortedSet and equality

Question

I am a bit puzzled about the behaviour of SortedSet, see following example:

public class Blah
{
    public double Value { get; private set; }

    public Blah(double value)
    {
        Value = value;
    }
}

public class BlahComparer : Comparer<Blah>
{
    public override int Compare(Blah x, Blah y)
    {
        return Comparer<double>.Default.Compare(x.Value, y.Value);
    }
}

public static void main()
{
    var blahs = new List<Blah> {new Blah(1), new Blah(2), 
                                new Blah(3), new Blah(2)}

    //contains all 4 entries
    var set = new HashSet<Blah>(blahs); 

    //contains only Blah(1), Blah(2), Blah(3)
    var sortedset = new SortedSet<Blah>(blahs, new BlahComparer());
}

So SortedSet discards entries if Compare(x,y) returns 0. Can I prevent this, such that my SortedSet behaves like HashSet and discards entries only if Equals() returns true?

The [docs for Comparer](http://msdn.microsoft.com/en-us/library/2y07t0wt.aspx) do say that 0 means 'x equals y', though, not 'no ordering'. I guess you could compare the reference values of x and y as well if the `.Value` s match. — Rup, Dec 22 '11 at 12:57

score 10 · Answer 1 · edited Jun 20 '20 at 09:12

Description

SortedSet: You have many elements you need to store, and you want to store them in a sorted order and also eliminate all duplicates from the data structure. The SortedSet type, which is part of the System.Collections.Generic namespace in the C# language and .NET Framework, provides this functionality.

According to MSDN Compare method returns

Less than zero if x is less than y.
Zero if x equals y.
Greater than zero if x is greater than y.

More Information

Update

If your Bla class implements IComparable and you want your list sorted you can do this.

var blahs = new List<Blah> {new Blah(1), new Blah(2), 
                            new Blah(3), new Blah(2)};
blahs.Sort();

If your Bla class NOT implements IComparable and you want your list sorted you can use Linq (System.Linq namespace) for that.

blahs = blahs.OrderBy(x => x.MyProperty).ToList();

thank you for the bold "eliminate all duplicates". when implementing the IComparer must be certain in 200% before returning "0" — ilansch, Jun 23 '13 at 12:38

score 5 · Accepted Answer · answered Dec 22 '11 at 13:35

You can do this if you provide an alternate comparison when the Values are equal and the Compare method would otherwise return 0. In most cases this would probably just defer the problem instead of solving it. As others have noted, the SortedSet discards duplicates and when you provide a custom comparer it uses that to determine duplicity.

    static void Main(string[] args)
    {
        var blahs = new List<Blah>
                        {
                            new Blah(1, 0), new Blah(2, 1),
                            new Blah(3, 2), new Blah(2, 3)
                        };

        blahs.Add(blahs[0]);

        //contains all 4 entries
        var set = new HashSet<Blah>(blahs);

        //contains all 4 entries
        var sortedset = new SortedSet<Blah>(blahs, new BlahComparer());

    }
}

public class Blah
{
    public double Value { get; private set; }

    public Blah(double value, int index)
    {
        Value = value;
        Index = index;
    }

    public int Index { get; private set; }

    public override string ToString()
    {
        return Value.ToString();
    }
}

public class BlahComparer : Comparer<Blah>
{
    public override int Compare(Blah x, Blah y)
    {
        // needs null checks
        var referenceEquals = ReferenceEquals(x, y);
        if (referenceEquals)
        {
            return 0;
        }
        var compare = Comparer<double>.Default.Compare(x.Value, y.Value);
        if (compare == 0)
        {
            compare = Comparer<int>.Default.Compare(x.Index, y.Index);
        }
        return compare;
    }
}

score 3 · Answer 3 · answered Dec 22 '11 at 13:04

3

You can't find the other Blah(2) because you're using a Set.

Set - A collection of well defined and **distinct** objects

MultiSet, for instance, allows duplicate objects.

answered Dec 22 '11 at 13:04

Shai

25,159
9
44
67

user764754 · Answer 4 · 2022-11-30T14:48:27.907

Sounds what you want is property-based sorting, but duplicate checking should be based on reference equality. To accomplish this (and if you don't mind that the memory consumption of your comparer can increase over time) we can add a fallback to the comparer that calculates the compare result based on IDs unique to the instances:

public class BlahComparer : Comparer<Blah>
{
    private readonly ObjectIDGenerator _idGenerator = new();

    public override int Compare(Blah x, Blah y)
    {
        int compareResult = Comparer<double>.Default.Compare(x.Value, y.Value);

        if (compareResult == 0)
        {
            // Comparing hash codes is optional and is only done in order to potentially avoid using _idGenerator further below which is better for memory consumption.
            compareResult =
                Comparer<int>.Default.Compare(RuntimeHelpers.GetHashCode(x), RuntimeHelpers.GetHashCode(y));

            if (compareResult == 0)
            {
                // HashCodes are the same but it might actually still be two different objects, so compare unique IDs:
                compareResult = Comparer<long>.Default.Compare(_idGenerator.GetId(x, out bool _), _idGenerator.GetId(y, out bool _)); // This increases the memory consumption of the comparer for every newly encountered Blah
            }
        }

        return compareResult;
    }
}

C# SortedSet and equality

4 Answers4

Description

More Information

Update

Linked

Related