Why does C# let me compile sort code when it doesnt know how to sort

Question

I thought it was odd that C# let me call sort on my class and not specify a way to sort them nor write a compare overload. When i ran this code this error popped up

List<MyClass> myClassArray= new List<MyClass>();
//myClassArray.add(...);
myClassArray.Sort();

An unhandled exception of type 'System.InvalidOperationException' occurred in mscorlib.dll

Additional information: Failed to compare two elements in the array.

Why does C# let me compile this code when it doesnt know how to sort this! -edit-

Codex ask why it does this. I wrote a theory on why it does it in my comments. Here some example code.

class A : IComparable<A>
{
    public int CompareTo(A a) { return 0; }
}
class C //: IComparable<A>
{
    public int CompareTo(A a) { return 0; }
}
    static void test()
    {
        A a = new A();
        bool b;
        C c = new C();

        object o = a;
        IComparable<A> ia = (IComparable<A>)o;
        b = ia == ia;

        o = c;
        IComparable<A> ic = (IComparable<A>)o;
        b = ic == ic;

        //uncomment this to get a compile time error
        //IComparable<A> ic2 = c;
        return;
    }

If you uncomment the line before return, you'll get a compile time error. When you uncomment IComparable in class c, it will compile and work.

Answer 1

There's no constraint on the generic parameter of List<T> requiring it to implement IComparable<T>. If there were, it would (sort of) guarantee that elements could be sorted, but you wouldn't be able to use List<T> to hold anything that didn't implement IComparable. And since you probably won't be sorting every list you create, this is the right decision.

Answer 2

Sort should be checking to see if your object implements IComparable. This is a run time check, and since you presumably don't implement it the default comparer doesn't know what to do with your objects, so it throws the exception.

It lets it compile because this isn't a language feature, its a framework feature.

Answer 3

The Sort() method is part of the IList interface, and can operate on any list of objects, even objects that aren't of the same type:

ArrayList arl = new ArrayList();
arl.Sort(); // what's in arl?  strings?  ints?  who knows (not the compiler)

So it doesn't really have an effective way ahead of time to know what objects are in your list, or whether or not it makes sense to compare them. It trusts you to take care of that.

As a result, Sort() feels sort of old and stuffy; in C# 3.0 it's largely subsumed by Enumerable.OrderBy().

Answer 4

Just for additional info; essentially, it uses Comparer<T>.Default to do the comparisons. This implements IComparer<T>, and can compare 2 objects of type T. The actual implementation is selected the first time you ask for it (per T); there are a number of patterns that the framework uses to pick the implementation - for example, classes, "regular" structs, and Nullable<T> are all handled separately. Likewise, it makes choices based on whether T implements IComparable<T>, IComparable, or neither (in which case it throws an exception).

This provides a very easy way to do "duck type" sorting. Likewise, there is also an EqualityComparer<T>.Default that checks for IEquatable<T>, defaulting to object.Equals otherwise.

Answer 5

C# arguably could have just have some baked in notion in System.Object about how you order objects like it did with Equals to compare them for identity.

Unfortunately, this leads to concerns about intensionality vs. extensionality, localizationm etc.

There is an IComparable<T> interface, but the built-in value types can't implement interfaces like that.

Therefore, there is no good way to just look at a type at compile time and know definitively if it has a meaningful ordering. =(

The mechanism that has evolved in C# is to use the IComparer<T> instance that is returned by Comparer<T>.Default and get a runtime error when you try to sort something which lacks an ordering.

By allowing multiple IComparers and IComparer<T>s, you can have a notion of multiple alternative orderings that work on the same type, so that much is good, but all is not well.

Internally, c# uses a bunch of rules to find Comparer<T>.Default, which it handles differently if T is an instance of IComparable<T> or is of the form Nullable<T>, etc.

e.g. the code from system/collections/generic/comparer.cs:

    public static Comparer<T> Default {
        get {
            Comparer<T> comparer = defaultComparer;
            if (comparer == null) {
                comparer = CreateComparer();
                defaultComparer = comparer;
            }
            return comparer;
        }
    }

    private static Comparer<T> CreateComparer() {
        Type t = typeof(T);
        // If T implements IComparable<T> return a GenericComparer<T>
        if (typeof(IComparable<T>).IsAssignableFrom(t)) {
            //return (Comparer<T>)Activator.CreateInstance(typeof(GenericComparer<>).MakeGenericType(t));
            return (Comparer<T>)(typeof(GenericComparer<int>).TypeHandle.CreateInstanceForAnotherGenericParameter(t));
        }
        // If T is a Nullable<U> where U implements IComparable<U> return a NullableComparer<U>
        if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
            Type u = t.GetGenericArguments()[0];
            if (typeof(IComparable<>).MakeGenericType(u).IsAssignableFrom(u)) {
                //return (Comparer<T>)Activator.CreateInstance(typeof(NullableComparer<>).MakeGenericType(u));
                return (Comparer<T>)(typeof(NullableComparer<int>).TypeHandle.CreateInstanceForAnotherGenericParameter(u));                
            }
        }
        // Otherwise return an ObjectComparer<T>
        return new ObjectComparer<T>();
    }

In essence, this lets Microsoft gradually add special cases for their own code, but unfortunately the code that results from just using Comparer<T>.Default for a custom IComparable<T> instance is pretty abysmal.

The Sort method on IList<T>, presumes that Comparer<T>.Default will come up with something it can use to compare your objects, but it has no way to look at the type T and tell that it does, so it assumes it is safe and only realizes later at runtime that MyClass isn't playing along.