C# Generics

Article
04/11/2006

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.

.NET 2 generics: the big picture

Declaring several parameter types

It can be useful to parameterize a type using several types. C#2 offers this feature. For example, as the following example shows, it is possible to implement a dictionary class which gives to the client the choice of types for both the key and the values:

 class DictionaryEntry<K,V>{
   public K Key;
   public V Value;
}
class Dictionary<K,V>{
   private DictionaryEntry<K,V>[] m_ItemsArray;
   public void Insert( DictionaryEntry<K,V> entry ) {...}
   public V Get(K key) {...}
   ...
}

Open and closed generic types

A generic type is a type that is parameterized by one or several other types. For example Stack<T>, Stack<int>, Dictionary<K,V>, Dictionary<int,V>, Dictionary<int,string> and Stack<Stack<T>> are generic types.

An open generic type is a generic type for which none of its parameter types are specified. For example Stack<T> and Dictionary<K,V> are open generic types.

A closed generic type is a generic type for which all the type parameters are specified. For example, Stack<int>, Dictionary<int,string> and Stack<Stack<int>> are closed generic types.

A generic type is compiled into a single type within its assembly. If we were to analyze the assembly which contains the Stack<T> open generic type in a certain assembly, we notice that the compilation only produced a single class even though we may be using the following closed generic types Stack<int>, Stack<bool>, Stack<double>, Stack<string>, Stack<object> and Stack<IDispose>.

However, during execution, the CLR will create and use several versions of the Stack<T> class. More precisely, the CLR uses a same version of Stack<T> common to all the parameters of a reference type and one version of Stack<T> for each parameter of a value type.

Figure 0–1: Different views of a generic type

.NET generics vs. C++ templates

Note for C++ coders: Those of you who know C++ have certainly made a correlation between the generics in C# to the templates of C++. Although that the functionalities are conceptually similar, this section will explain one of the fundamental differences:

Closed generic types generated by C++ templates are produced by the compiler and are contained in the component generated by the compiler.
Closed generic types generated by .NET are produced during execution by the JIT compiler and the underlying generic type is only present in one form in the assembly resulting from the compilation.

In other words, the notion of an open generic type exists in C#/.NET at both the code and runtime level while in C++ it only exists at the source code level.

The observation clearly shows one of the advantages of generics in C# since the size of the .NET components is actually reduced. This is not a small saving as the phenomenon known as code-bloat, can lead to code size problems (and that is without taking into account the avalanche of warnings produced by some C++ compilers). Also, this component based programming model offered by .NET is even more powerful with this implementation since an open generic type can be closed by a type which exists in another component.

There can still be some code-bloat in .NET but to a lesser extent. In fact, the generic types which are closed by the CLR will never be collected by the garbage collector or by another entity. They reside in their AppDomain until it is destroyed. In certain rare cases which can be resolved by manually unloading the AppDomain, there can be a memory bloat. A good point for generics in .NET is that a closed generic type is only created as late as possible, when it is used for the first time. In addition, the number of classes generated at runtime is bound by the number of closed generic classes used in the source code.

A similar problem which may be more cumbersome is when we use the ngen.exe tool to improve performance by performing the work of the JIT compiler before execution. In this case, all the closed generic types referenced in the source code will be created. The ngen.exe tool is incapable of distinguishing whether certain closed generic types referenced in the source code will be effectively used.

Visibility of a generic type

The visibility of a generic type is the intersection of the generic type with the visibility of the parameter types. If the visibility of all the C, T1, T2 and T3 types is set to public, then the visibility of C<T1,T2,T3> is also public; but if the visibility of only one of these types is private, then the visibility of C<T1,T2,T3> is private.

The astute reader may have realized by now that with generics, we can obtain a type of visibility which wasn't accessible in C# but know by the CLR which is protected AND internal (visible only in the derived classes of a same assembly). However know that such a type is constructed during the execution by the CLR and thus does not create an incoherency in the C# language.

Example 4

 internal class ClassInternal { }
public class ClassFoo{
   protected class ClassProtected { }
   public class ClassPublic<U,V> { }

   // The C# compiler checks that the
   // 'ClassPublic<ClassInternal,ClassProtected>' type is not used
   // outside this class and outside its derived classes defined in
   // the current assembly. However, you can't assign any other
   // visibility than 'private' to this field.
   private ClassPublic<ClassInternal,ClassProtected> foo;
}

Generic structure and interface

In addition to generic classes, C#2 allows to defining generic structures and interfaces. This feature does not require any special remarks with the exception that a type cannot implement the same generic interface with different parameter types. For example, the following program will not compile:

Example 5

 interface I<T> { void Fct(); }
// Compilation Error:
// 'C<U,V>' cannot implement both 'I<U>' and 'I<V>' because they
// may unify for some type parameter substitutions.
class C<U, V> : I<U>, I<V> {
   void I<U>.Fct() { }
   void I<V>.Fct() { }
}

Aliases and generic types

The using directive can be used to create an alias on the name of a closed generic type. The scope of such a directive is to the current file if it is used outside of all namespaces. If not, it is restricted to the intersection of the current file and the namespace in which the alias is defined. For example:

 using TelephoneDirectory = Dictionary<TelephoneNumber, string>; 
class TelephoneNumber { }
class Dictionary<K, V>{ }
...
TelephoneDirectory telephoneDirectory = new TelephoneDirectory();

The preceding article is excerpted from the book Practical .NET2 and C#2 by Patrick Smacchia. Publisher: Paradoxal Press. ISBN: 0-9766132-2-0. (Browse and down

About the Author
Patrick Smacchia is a .NET MVP involved in software development for over 15 years. He is the author of Practical .NET2 and C#2 (https://www.PracticalDOT.NET), a .NET book conceived from real world experience with 647 compilable code listings. After graduating in mathematics and computer science, he has worked on software in a variety of fields including stock exchange at Societe Generale, airline ticket reservation system at Amadeus as well as a satellite base station at Alcatel. He's currently a software consultant and trainer on .NET technologies as well as the author of the freeware NDepend which provides numerous metrics and caveats on any compiled .NET (https://www.NDepend.com) application.

C# Generics

C# Generics

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

The problem of typing collection items with C#1

An ideal solution using C#2 generics

.NET 2 generics: the big picture

Declaring several parameter types

Open and closed generic types

.NET generics vs. C++ templates

Visibility of a generic type

Generic structure and interface

Aliases and generic types

Additional resources