Dictionary doesn't use class's compare method

Question

A few days ago, I asked a question about dictionary implementations in C# for a class I had written. I have a dictionary that has keys of class Interval and values of class Line2D. My updated implementation of interval looks like this:

public class Interval : ICloneable, IComparable, IComparable<Interval>, IComparable<double>
{
    public Interval()
    {

    }
    public Interval(Interval interval)
    {
        this.CopyFrom<Interval>(interval);
    }
    public Interval(double start, double end)
    {
        Start = start;
        End = end;
    }

    // Properties
    public double Start { get; set; } = double.NaN;
    public double End { get; set; } = double.NaN;
    public double Span => End - Start;

    // Methods
    public object Clone() => MemberwiseClone();

    public int CompareTo(object obj)
    {
        if (obj is Interval iObj)
        {
            return CompareTo(iObj);
        }
        return 1;
    }

    public int CompareTo([AllowNull] Interval other)
    {
        if (Start == other.Start && End == other.End)
        {
            return 0;
        }
        else if (End <= other.Start)
        {
            return -1;
        }
        else if (other.End <= Start)
        {
            return 1;
        }
        else
        {
            throw new ArgumentException("Interval must not overlap with this one.", nameof(other));
        }
        // Old implementation
        //if (Start < other.Start)
        //{
        //    return -1;
        //}
        //else if (Start > other.Start)
        //{
        //    return 1;
        //}
        //else
        //{
        //    return 0;
        //}
    }

    public int CompareTo([AllowNull] double other)
        => Contains(other) ? 0 : (other < Start ? 1 : -1);

    public bool Contains(double x) => Start <= x && x <= End;
    public override string ToString() => $"[{Start}, {End}]";
}

So if I create a dictionary where the keys are Interval objects, I thought my CompareTo methods would cover the situation where two intervals have the same starting point and end point. However, this is not the case.

var testDict = new Dictionary<Interval, int>();
var testInterval1 = new Interval(0, 1);
var testInterval2 = new Interval(testInterval1); // Should be identical
testDict[testInterval1] = 5;
var contains = testDict.ContainsKey(testInterval2); // This is false when it should be true;
testDict[testInterval2] = 10; // This shouldn't work but it does

Why doesn't the default comparer hop into my CompareTo methods during execution?

Answer 1

Because Dictionary doesn't use IComparer<T>, it uses IEqualityComparer<T>.

From the Remarks section of the official documentation of Dictionary<TKey,TValue>:

Dictionary<TKey,TValue> requires an equality implementation to determine whether keys are equal. You can specify an implementation of the IEqualityComparer<T> generic interface by using a constructor that accepts a comparer parameter; if you do not specify an implementation, the default generic equality comparer EqualityComparer<T>.Default is used. If type TKey implements the System.IEquatable<T> generic interface, the default equality comparer uses that implementation.

Note that it's not your type that needs to implement the IEqualityComparer<T> interface - but instead, it can be passed as a dependency to the Dictionary's constructor.

If you want your type to be compared in a specific way, you should implement the IEquatable<T> interface in your type.

Note: If you implement the IEquatable<T> interface, it's recommended to also override the Equals(object) and GetHashCode() methods, and overload the == and != operators, as explained in Notes to Implementers:

Replace the type parameter of the IEquatable<T> interface with the type that is implementing this interface. If you implement IEquatable<T>, you should also override the base class implementations of Equals(Object) and GetHashCode() so that their behavior is consistent with that of the Equals(T) method. If you do override Equals(Object), your overridden implementation is also called in calls to the static Equals(System.Object, System.Object) method on your class. In addition, you should overload the op_Equality and op_Inequality operators. This ensures that all tests for equality return consistent results.

Answer 2

To use complex values as dictionary keys, you need to specifically implement GetHashCode() and Equals(). CompareTo is not relevant for this use-case.

Answer 3

I think Dictionary uses Equals and GetHashCode methods of the class, so you need to override those. See this question

Answer 4

Comparable != equatable

Equatable checks are able to tell you if two items are equal or not. Comparable checks are able to tell you which item ranks higher than the other.

While comparability inherently requires equatability (because if you can't tell things apart, you cannot rank them), equatability does not require comparability. Since the dictionary only cares about equating its key values, it completely ignores whether your Interval class is comparable or not.

A dictionary contains its own equality comparer. By default, it uses the default equality comparer, and the default equality comparer relies on IEquatable<T>, not IComparable<T>.

Note
MSDN is incorrect in its claim that it uses IEquatable<T>.Equals to check for equality. When you test this with a dictionary, it's in fact IEquatable<T>.GetHashCode that is used to check equality between dictionary key values.

In other words: a dictionary checks if key values are (not) equal to each other, it does not attempt to order/rank the key values.

There are two possible solutions here:

• Implement IEquatable<T> on your Interval class and rely on the dictionary's default equality comparer
• Give your dictionary a custom equality comparer where you can define your own equality comparison logic (MSDN link)