C# Generics

The following article is excerpted from the book Practical .NET2 and C#2.

C# Generics

Without any doubt, generics is the flagship functionality in .NET 2 from the language’s perspective. After explaining what generics are, we will examine the implication of its support at the level of the C#2 language, the CLR and the framework. To start off, let us mention that all generic types and methods are CLS compliant and can thus be used across all CLR v2 languages.

A C#1 problem and how to solve it with .NET 2 generics

The problem of typing collection items with C#1

Let’s assume that we have to implement a Stack class which allows stacking and unstacking elements. To simplify our code, we will assume that the stack cannot contain more than a certain number of elements. This constraint allows us to internally use a C# array. Here is an implementation of this Stack class:

Example 1

class Stack{
   private object[] m_ItemsArray;
   private int m_Index = 0;
   public const int MAX_SIZE = 100;
   public Stack() { m_ItemsArray = new object[MAX_SIZE]; }
   public object Pop() {
      if (m_Index ==0 )
         throw new System.InvalidOperationException(
            "Can't pop an empty stack.");
      return m_ItemsArray[--m_Index];
   }
   public void Push( object item ) {
      if(m_Index == MAX_SIZE)
         throw new System.StackOverflowException(
            "Can't push an item on a full stack.");
      m_ItemsArray[m_Index++] = item;
   }
}

This implementation suffers from three major problems.

  • First of all, the client of the Stack class must explicitly cast all elements obtained from the stack. For example:

    ...
    Stack stack = new Stack();
    stack.Push(1234);
    int number = (int)stack.Pop();
    ...
    
  • A second problem which is less obvious is from a performance perspective. We must be aware that when we use our Stack class with value type elements, we will implicitly perform a boxing operation when inserting elements and an unboxing operation when removing an element. This is highlighted by the following IL code:

    L_0000: newobj instance void Stack::.ctor()
    L_0005: stloc.0
    L_0006: ldloc.0
    L_0007: ldc.i4 1234
    L_000c: box int32
    L_0011: callvirt instance void Stack::Push(object)
    L_0016: nop
    L_0017: ldloc.0
    L_0018: callvirt instance object Stack::Pop()
    L_001d: unbox int32
    L_0022: ldind.i4
    L_0023: stloc.1
    L_0024: ret
    
  • Finally, a third problem comes from the fact that we can store elements of different types within a same instance of the Stack class. Generally, we wish to have a stack of elements with a common type. This feature can easily lead to casting errors which are only found during the execution as with the following example:

    ...
    Stack stack = new Stack();
    stack.Push("1234");
    int number = (int)stack.Pop();    // Raise an InvalidCastException.
    ...
    

When a casting problem is not detected during compilation but can provoke an exception at run-time we say that the code is not type-safe. In software development, as well as any other discipline, the earlier an error is detected the least costly will this error be. This means that whenever possible, you must make sure to have type-safe code as this allows the detection of problems early on, at compile-time.

It is possible to implement our stack in a type-safe way. In fact, we could have implemented a StackOfInt class which describes a stack containing only integers, a StackOfSring class which only contains strings,…

Example 2

class StackOfInt {
   private int[] m_ItemsArray;
   private int m_Index = 0;
   public const int MAX_SIZE = 100;
   public StackOfInt(){ m_ItemsArray = new int[MAX_SIZE]; }
   public int Pop() { /*...*/  return -1; }
   public void Push(int item) { /*...*/ }
}
class StackOfString {
   private string[] m_ItemsArray;
   private int m_Index = 0;
   public const int MAX_SIZE = 100;
   public StackOfString(){ m_ItemsArray = new string[MAX_SIZE]; }
   public string Pop() {/*...*/ return null; }
   public void Push(string item) {/*...*/}
}

Although it is type-safe and that is solves both the casting and performance problems, this solution is clearly unsatisfactory. It implies code duplication since the same stack logic is implemented by several classes. This means more code to maintain and hence a loss of productivity.

An ideal solution using C#2 generics

C#2 offers an elegant solution to the problem exposed in the previous section through the introduction of generic types. Concretely, we can implement a stack of elements of type T by giving the client the freedom to specify the T type when they instantiate the class. For example:

Example 3

class Stack<T>{
   private T[] m_ItemsArray;
   private int m_Index = 0;
   public const int MAX_SIZE = 100;
   public Stack(){ m_ItemsArray = new T[MAX_SIZE]; }
   public T Pop(){
      if (m_Index ==0 )
         throw new System.InvalidOperationException(
            "Can't pop an empty stack.");
      return m_ItemsArray[--m_Index];
   }
   public void Push(T item) {
      if(m_Index == MAX_SIZE)
         throw new System.StackOverflowException(
            "Can't push an item on a full stack.");
      m_ItemsArray[m_Index++] = item;
   }
}
class Program{
   static void Main(){
      Stack<int> stack = new Stack<int>();
      stack.Push(1234);
      int number = stack.Pop(); // Don't need any awkward cast.
      stack.Push(5678);
      string sNumber = stack.Pop();  // Compilation Error:
         // Cannot implicitly convert type 'int' to 'string'.
   }
}

This solution does not suffer from any of the problems discussed earlier.

  • The client does not need to cast an element popped from the stack.
  • This solution is efficient as it does not require boxing/unboxing operations.
  • The client writes type-safe code. There is no possibility of having a stack with various types during execution. In our example, the compiler prevents the insertion of any element which is not an int or which cannot be implicitly converted into an int.
  • There is no code duplication.

Understand that in our example, the generic class is Stack<T> while T is the parameter type for our class. We sometimes used the parametric polymorphism term to talk about generics. In fact, our Stack<T> class can take several forms (Stack<int>, Stack<string> etc). It is then polymorphic and parameterized by one type. Caution, do not confuse this with the polymorphism of object oriented languages which allows the manipulation of various types of objects (i.e. instance objects from different classes) through a same interface.

To summarize, the Stack<T> class represents any kind of stack while the Stack class represents a stack of anything.

More by Author

Must Read