Generics and arrays - type specific operations
Written by Mike James   
Tuesday, 01 March 2011
Article Index
Generics and arrays - type specific operations
Find

Generics are great but in C# they seem to be limited in what they can do - specifically you can't have an operation that depends on the type actually used. However generic delegates provide a way of implementing type dependent operations in a generic method. This article takes a look at how this works using the Array as an example.

 

We all know and love arrays but .NET has some data structures and facilities that are just a touch more sophisticated than the simple array.  What is often not realised is that the introduction of generics has changed the way that even simple things like arrays can be used. In this article we look at the way generic alternatives to the usual array methods are used. It also provides an interesting example of non-generic v generic approaches to coding simple things.

In particular it provides an example of how we can overcome one of the big problems in using generics - type specific operations. Using generic delegates you can implement a generic algorithm that uses operations which depend on the type specified when the generic is used.

Array sorting

The .NET array was already a fairly sophisticated construct compared to simple languages because it treats everything as an object. This means that arrays not only store data they also can have methods that do things. In most cases however these methods are provided by the static Array object. 

For example:

int[] A = new int[50];
//put some data into A
Array.Sort(A);

results in the array A being sorted into ascending order using a QuickSort.

Thing are a little more sophisticated than the appear because you can see the order relation used in the sort. The point is that you can have an array of strongly typed objects and in this case you need to defined what a sorted order is.

To define the order relation used in the sort you need to implement an object with an IComparer interface. This defines a Compare method that returns –1, 0, or 1 depending on the result of the compare:

private class CMyCompare : IComparer
{
int IComparer.Compare(Object x, Object y)
{

The problem now is that we have to do the comparison between x and y but this is difficult without knowing what types they are. Without generics this is the only way you can define the interface.

The simplest solution is to cast to the type that you know is stored in the array and then use the type’s CompareTo method:

 

private class CMyCompare : IComparer
{
int IComparer.Compare(Object x, Object y)
{
 return (((int)y).CompareTo((int)x));
}
}
Of course this is really only useful if you are working with your own classes and can implement your own CompareTo method. With this definition we can sort the array into descending order using:

 

Array.Sort(A, new CMyCompare());

The wider point being made is that without using generics this is the only way the job can be done. You need an interface to define the form of the function to be used and you have to cast to actually do the work that makes use of the nature of the objects actually being passed. This clearly isn't type safe at compile time as the casts cannot be checked but it can be made type safe at runtime by adding code to make sure the objects are of a type you can work with.

Generics

This is all good but it’s pre-generics which were introduced as long ago as .NET 2.0. Arguably generics provide a better way of implementing sorting methods that work with any type. The big problem with generics is that you can't use them to do things that are type specific. That is if you have two objects that are specified as generic you can't add them together even if in they support the operation. That is you can't write something like:

T x;
T y;
T z;
z=x+y;

because the type of T isn't specified.

This seems to reduce the usefulness of generics. But this isn't always the case because you can define operations on generics using a generic delegate i.e. a method type with a generic signature. The concrete operation is then provided by a specific instance of the delegate that has a fully defined signature that fits the generic specification.

This is a complicated pattern but it seems so much simpler when you see it in action. Let's take a look at the way the Array generic methods work.

 

In .NET a number of new generic sort methods were introduced. For example:

public static void Sort<T> (
T[] array,
   Comparison<T> comparison
)

This uses the generic Comparison delegate to supply the order relation used in the sort:

public delegate int Comparison<T> (T x,T y)

To implement the same sort as we did using IComparer all we have to do is write a Comparison function - no interfaces necessary:

public int MyCompare(int x, int y)
{
return (((int)y).CompareTo((int)x));
}

Now as long as we select the generic sort i.e. Sort<T> all we have to change is - well nothing much at all:

Array.Sort(A, MyCompare);

Notice this differs slightly from the use of generics we normally encounter. The MyCompare function simply has to have the correct signature and the system uses the type information to instantiate the generic within the Sort method.

This becomes slightly clearer if you write it out fully as:

Array.Sort<int>(
A,new Comparison<int>(MyCompare));

which instantiates the Sort definition to:

public static void Sort (
      int [] array,
      Comparison< int > comparison
)

To understand what a generic definition actually produces it is often helpful to actually write out the result of setting the type parameters to particular values.

In turn the definition of Comparison is:

public delegate int 
Comparison (int x,int y)

This is, of course, the signature of the function that we are actually passing. Notice that the shorthand way of writing the function call saves specifying the data type twice and it also automatically creates the delegate using the “method group conversion” facility.

Banner

<ASIN:0470495995>

<ASIN:0672330792>

<ASIN:1430229799>

<ASIN:0262201755>

<ASIN:0596800959>



Last Updated ( Tuesday, 01 March 2011 )