Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C# BinarySearch breaks when inheriting from something that implements IComparable<T>?

In .NET the BinarySearch algorithm (in Lists, Arrays, etc.) appears to fail if the items you are trying to search inherit from an IComparable instead of implementing it directly:

List<B> foo = new List<B>(); // B inherits from A, which implements IComparable<A>
foo.Add(new B());
foo.BinarySearch(new B());   // InvalidOperationException, "Failed to compare two elements in the array."

Where:

public abstract class A : IComparable<A>
{
    public int x;

    public int CompareTo(A other)
    {
        return x.CompareTo(other.x);
    }
}

public class B : A {}

Is there a way around this? Implementing CompareTo(B other) in class B doesn't seem to work.

like image 573
Ender Avatar asked May 02 '10 04:05

Ender


1 Answers

The documentation makes this quite clear:

checks whether type T implements the IComparable generic interface and uses that implementation, if available. If not, Comparer.Default checks whether type T implements the IComparable interface. If type T does not implement either interface, Comparer.Default throws an InvalidOperationException.

So, a simple solution is to implement the non-generic interface IComparable.
Adding CompareTo(B other) will work for you, as long as you also implement IComparable<B> - you probably forgot that bit.

An interesting solution is to compile the code using C# 4, where it runs without any errors. C# 4 introduces Generic Covariance: public interface IComparable<in T> vs public interface IComparable<T>, and the posted code works as expected.

like image 93
Kobi Avatar answered Sep 18 '22 12:09

Kobi