Comparisons with Generics

Generics in C# introduces restrictions on the equality operator. In a generic class with a type parameter T, it is not possible to compare two operands with the equality operator, unless one of the operators is null.

The following won't compile, because equality is not generally defined for value types and also because equality is an overloadable operator.

public bool Compare<T>(T value1, T value2)
{
    return value1==value2;
}

However, comparing a value against null will compile, despite the fact that valuetypes are not nullable and the fact overloadable equality operators do not necessarily have treat null comparisons in the standard way. For valuetypes, a null equality test always returns false and a null inequality test always returns true. 

public bool IsNull<T>(T value1)
{
    return value1==null;
}

While constructing a generic collection class that supports the IList<T> interface, I was initially at a loss as to how to write IndexOf and Contains without having to revert to the standard Object.Equals instance method, that always performs boxing conversions for value types and unnecessary casts for reference types. As I mentioned earlier, the equality operator is not available in generic classes and methods.

My initial solution was to add an IComparable constraint to the collection. Unfortunately, this solution has the disadvantage of either restricting the objects allowable in the collection or adding IComparable<T> support to classes where ordering does not make much sense. (Even then, it is not possible to allow some system classes like enums into the collection, because IComparable support is omitted.) If specialization was supported in generics, I could build alternate versions of the same generic class.

I wondered how the standard libraries implemented IndexOf and Contains. It turns out that they used the new System.Collection.Generics.Comparer<T> class, which has a static property, Comparer<T>.Default, that sports both a Compare and an Equals method, each taking two parameters. For the Compare method, this class uses the IComparable<T> interface, if available, otherwise it reverts to the non-generic IComparable interface. For the Equals method, the generic IComparable<T> interface is used, if available; if not, it reverts to the object.Equals(method)/

public bool Compare<T>(T value1, T value2)
{
   return Comparer<T>.Default.Compare(value1, value2);
}

Comparer<T>.Default refers to a generic static field. If the static field is null, it constructs and places in the field, either a GenericComparer<T> or ObjectComparer<T>, depending on whether T supports IComparable<T>.

 A generic static field is like a dictionary or hashtable with a type value as a key, except that it is more efficient to access as the JIT compiler can hardcode the address of the static field directly into the generated code rather than compute the type's hash code and probe buckets. Each closed generic type has its own copy of a generic static field, in which it can store its own data independently from that of all other possible closed generic types.

 

 

Comments

[Tony Chow]

Your article made me wonder how GenericEqualityComparer invokes IEquality on a value type without boxing. This led to the following blog entry:

http://www.bluetentacle.lunarpages.com/blog/?itemid=3