Generics Problem Statement

Consider an everyday data structure such as a stack, providing the classic Push( ) and Pop( ) methods. When you develop a general-purpose stack, you would probably like to use it to store instances of various types. Under C# 1.1, you have to use an object-based stack, meaning that the internal data type used in the stack is an amorphous object, and the stack methods interact with objects:

     public class Stack     {        object[] m_Items;        public void Push(object item)        {...}        public object Pop( )        {...}     } 

Example D-1 shows the full implementation of the object-based stack.

Example D-1. An object-based stack

 public class Stack {    const int DefaultSize = 100;    readonly int m_Size;    int m_StackPointer = 0;    object[] m_Items;    public Stack( ) : this(DefaultSize)    {}      public Stack(int size)    {       m_Size = size;       m_Items = new object[m_Size];    }    public void Push(object item)    {       if(m_StackPointer >= m_Size)       {          throw new StackOverflowException( );       }            m_Items[m_StackPointer] = item;       m_StackPointer++;    }    public object Pop( )    {       m_StackPointer--;       if(m_StackPointer >= 0)       {          return m_Items[m_StackPointer];       }       else       {          m_StackPointer = 0;          throw new InvalidOperationException("Cannot pop an empty stack");       }    } } 

Because object is the canonical .NET base type, you can use the object-based stack to hold any type of items, such as integers:

     Stack stack = new Stack( );     stack.Push(1);     stack.Push(2);     int number = (int)stack.Pop( ); 

However, there are two problems with object-based solutions. The first issue is performance. When you use value types, you have to box them in order to push and store them, and you must unbox the value types when popping them off the stack. Boxing and unboxing incurs a significant performance penalty in its own right, but it also increases the pressure on the managed heap, resulting in more garbage collections, which is not great for performance either. Even if you use reference types instead of value types, there is still a performance penalty because you have to cast from an object to the actual type you interact with and incur the casting cost:

     Stack stack = new Stack( );     stack.Push("1");     string number = (string)stack.Pop( ); 

The second (and often more severe) problem with the object-based solution is type safety. Because the compiler lets you cast anything to and from object, you lose compile-time type safety. For example, the following code compiles fine but raises an invalid cast exception at runtime:

     Stack stack = new Stack( );     stack.Push(1);     //This compiles, but is not type safe, and will throw an exception:     string number = (string)stack.Pop( ); 

You can overcome these two problems by providing a type-specific (and hence type-safe) performance stack. For integers, you can implement and use the IntStack:

     public class IntStack     {        int[] m_Items;        public void Push(int item)        {...}        public int Pop( )        {...}     }     IntStack stack = new IntStack( );     stack.Push(1);     int number = stack.Pop( ); 

For strings, you would implement the StringStack:

     public class StringStack     {        string[] m_Items;        public void Push(string item)        {...}        public string Pop( )        {...}     }     StringStack stack = new StringStack( );     stack.Push("1");     string number = stack.Pop( ); 

And so on. Unfortunately, solving the performance and type-safety problems this way introduces a third, and just as serious, problem: productivity impact. Writing a type-specific data structure is a tedious, repetitive, and error-prone task. When you fix a defect in the data structure, you have to fix it not just in one place, but in as many places as there are type-specific duplicates of what is essentially the same data structure. In addition, there is no way to foresee the use of unknown or as-yet-undefined future types, so you have to keep an object-based data structure as well. As a result, most developers find type-specific data structures to be impractical and opt for using object-based data structures, in spite of their deficiencies.