7.4 Ordering Instances

The implementations of the collection classes' sorting and searching capabilities depend on certain facilities in the contained objects themselves. The most common of these are the ability to order the contained objects (used for sorting and efficient searching) and the ability to hash an object (to speed storage and retrieval in dictionary-based structures such as Hashtable). As with most other parts of the FCL's collections framework, this is accomplished via standardized interfaces and overridden virtual methods on System.Object.

7.4.1 The IComparable Interface

The IComparable interface allows one object to indicate its ordering relative to another instance of the same type. To allow sorting and searching of your types in an array, implement the IComparable interface, which looks like this:

public interface IComparable {
  int CompareTo(object rhs);
}

Implementation of this interface should follow the following semantic rules:

An example implementation of this interface might look like this:

public sealed class Person : IComparable {
  public string Name;
  public int Age;
  public int CompareTo(object o) {
// Check for null
    if (o=  =null) return 1;
// Check for concrete type match
    if (o.GetType( ) != this.GetType( ))
      throw new ArgumentException( );
// Sort instances by ascending Age
    Person rhs = (Person)o;
    if (Age < rhs.Age) return -1;
    if (Age > rhs.Age) return 1;
    return 0;
  }
}

Note that in this example Person is marked as sealed. This is intended to simplify implementation, which can be complex in the face of future, unexpected inheritance. Remember to always ensure that the rules in the semantic contract are followed, including the one that states you can only compare identical types. One way of enforcing this is by explicitly comparing the types using GetType( ), as the previous sample does. Additionally, ensure that comparing to a null reference doesn't throw an exception, but returns 0, which sorts the null entries to the front of the list.

Implementing IComparable allows you to provide a default ordering for a type. However, sometimes more than one ordering for a type is needed. This can be accomplished using implementations of the IComparer interface.

7.4.2 The IComparer Interface

The collection classes actually perform their sorting using an implementation of the IComparer interface, which compares two independent object instances for their relative ordering. The IComparer interface looks likes this:

public interface IComparer {
  int Compare(object x, object y);
}

You generally don't need to implement this interface, since a default implementation that delegates to the IComparable interface is already provided by the Comparer type (which is used by the Array class by default). However, if you wish to provide additional ordering options for a type, you can provide additional concrete implementations of the IComparer interface that performed type-specific comparisons (these are often implemented as nested helper types).