Primer on Generics

Introduction

Generics are often associated with C++ templates. Both use a sort of "parameterized types". Generics and C++ templates take very different approaches to how and when objects are instantiated, however. Generics are instantiated at runtime by the CLR, and templates are instantiated at compile-time. This fundamental difference is at the root of almost every point of variation between Generics and templates. This article will focus on Generics without going into C++ templates. I will go into a description of Generics and describe why the use of Generics improves performance and type-safety. The reader should notice that both technologies try to solve the same problem, yet are significantly different despite their underlying similarity.

Generics allow you to create a flexible data structure that allows you to define its data types at instantiation. That is, it doesn't have its data type defined ahead of time. Instead, each time you want to create a new instance of the generic data structure - whether it's a generic collection, a generic class, a generic property of a class, or a generic delegate - you pass in the data type that you want the data structure to adopt. So in a sense, passing data types into generic data structures is analogous to passing input parameters into methods, but instead of supplying a value, you are actually supplying a data type. Most examples of Generics involve the generic implementations of the System.Collections.Generic namespace. More specifically, all of the classes defined in the System.Collections namespace - the ArrayList, the SortedList, the Queue, the Stack, the HashTable, the BitArray, and so on -- all have implementations in the System.Collections.Generic namespace. So let's walk through an example as to why we would want to use Generics. Assume we want to store a bunch of objects in a collection. Inside the .NET Framework, the ArrayList class attempts to solve this problem. Because ArrayList does not know what kind of objects users might want to store, it simply stores instances of the Object class. As we know, everything in .NET is an Object; therefore ArrayList can store any type of object. Problem solved, huh?

Although a collection of objects does solve this problem, it introduces new ones. For example, if you wanted to store a collection of integers, you could just write up some code like this:

using System;
using System.Collections;
public sealed class Program {
    public static void Main() {
        ArrayList theInt32s = new ArrayList();
        theInt32s.Add(1);
        theInt32s.Add(2);
        theInt32s.Add(3);
        foreach (Object i in theInt32s)
        {
            Int32 number = (Int32)i;
            Console.WriteLine(i);
        }
    }
}

The obvious output:

1
2
3

OK. So far all is good. I created a collection and added integers to it. I can get the integers out by casting them from the Object that my collection returns. That is, I cast an object type to an Int32 type. But what happens if I add myInt32s.Add("4")? This would compile just fine but in my foreach loop, it will throw an exception because 4 is a string and not an integer. So why don't I write a class that just stores integers? You can with generic types. Generic types are types that take other type names to define them as a type. Instead of creating a collection that is strongly-typed to a specific type, I'll write a quick collection that can use any type:

public class MyList<t> : ICollection, IEnumerable
{
    private ArrayList _innerList = new ArrayList();
    public void Add(T val)
    {
        _innerList.Add(val);
    }
    public T this[int index]
    {
        get
        {
            return (T)_innerList[index];
        }
    }
#region ICollection Members
    // ....
#endregion

#region IEnumerable Members
    // ..
#endregion

Similar to passing a value to a method, we have passed a type to a class (stated crudely). The class is identical to the collection I created earlier, but instead of making it a collection of integers, I used a generic type parameter T. In every place I had integers, I now put the parameter T. T is replaced with the type during compilation. So I can use this class to create collections that are strongly typed to any valid .NET type, as shown in the generic List class. The generic List class is used to create a simple, type-safe ordered list of objects. For example, if you wanted to have a list of integers, you would create a List object specifying the integer type for the generic parameter. Once you create an instance of the generic List class, you can then perform the following actions:

• You can use Add to add items into the List, but the items must match the type specified in the generic type parameter of the List.
• You can use the indexer syntax to retrieve items from the List class. Note that properties either take or don't take parameters. Parameter-full properties are called indexers and are a means to access items in a class similar to accessing items in an array-like fashion.
• You can use the foreach syntax to iterate over the List.

Consider the three operations above and examine the code below:

using System;
using System.Collections.Generic;
public class Program {
    public static void Main() {
        List<int>  intList = new List<int>();
        intList.Add(1);
        intList.Add(2);
        intList.Add(3);
        int number = intList[0];
        foreach ( int i in intList)
        {
            Console.WriteLine(i);
        }
    }
}

Here is a more in depth example. Below is a class file that compiles in the .NET Framework using the "/t:library" switch to create a DLL. Look at the classes defined in this file, and then look at how the types are passed as parameters in the main program:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

public class HelloGenerics<t> {
    private T _thisTalker;

    public T Talker {
        get { return this._thisTalker; }
        set { this._thisTalker = value; }
    }

    public void SayHello() {
        string helloWorld = _thisTalker.ToString();
        Console.WriteLine(helloWorld);
    }
}

public class GermanSpeaker {
    public override string ToString() {
        return "Hallo Welt!";
    }
}

public class SpainishSpeaker {
    public override string ToString() {
        return "Hola Mundo!";
    }
}

public class EnglishSpeaker {
    public override string ToString() {
        return "Hello World!";
    }
}

public class APLSpeaker {
    public override string ToString() {
        return "!dlroW olleH";
    }
}

To compile: csc.exe /target:library HelloGenerics.cs.

Now examine the source file that passes the types:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

class Program {
    static void Main(string[] args) {
        HelloGenerics<germanspeaker> talker1 = 
                new HelloGenerics<germanspeaker>();
        talker1.Talker = new GermanSpeaker();
        talker1.SayHello();

        HelloGenerics<spainishspeaker> talker2 = 
                new HelloGenerics<spainishspeaker>();
        talker2.Talker = new SpainishSpeaker();
        talker2.SayHello();

        Console.ReadLine();
    }
}

To compile: csc.exe /r:HelloGenerics.dll program.cs.

The output:

C:\Windows\MICROS~1.NET\FRAMEW~1\V20~1.507>person.exe
Hallo Welt!
Hola Mundo!

In the main program, we passed two types: the Spanish Speaker and the German Speaker, which is why our output did not contain any English.

What About Type-Safety and Performance?

When a generic algorithm is used with a specific type, the compiler and the CLR understand this and ensure that only objects compatible with the specified data type are used within the algorithm. If you wanted to use the algorithm with value type instances, the CLR would have to box the value type instance prior to calling the members of the algorithm. Boxing causes memory allocations on the managed heap, which causes more frequent garbage collections, which in turn hurts performance. Value types are normally allocated inline as a sequence of bytes on the stack. To demonstrate how powerful Generics is, consider the example below that compares the type-safe ignorant, non-generic ArrayList algorithm compared with the performance of the generic List algorithm. This code was written by Jeffrey Richter and is shown in his book, "The CLR via C#", Second Edition:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

public static class Program {
   public static void Main() {
      ValueTypePerfTest();
      ReferenceTypePerfTest();
   }

   private static void ValueTypePerfTest() {
      const Int32 count = 10000000;

      using (new OperationTimer("List<int32>")) {
         List<int32> l = new List<int32>(count);
         for (Int32 n = 0; n < count; n++) {
            l.Add(n);
            Int32 x = l[n];
         }
         l = null;  // Make sure this gets GC'd
      }

      using (new OperationTimer("ArrayList of Int32")) {
         ArrayList a = new ArrayList();
         for (Int32 n = 0; n < count; n++) {
            a.Add(n);
            Int32 x = (Int32) a[n];
         }
         a = null;  // Make sure this gets GC'd
      }
   }

   static void ReferenceTypePerfTest() {
      const Int32 count = 10000000;

      using (new OperationTimer("List<string>")) {
         List<string> l = new List<string>();
         for (Int32 n = 0; n < count; n++) {
            l.Add("X");
            String x = l[n];
         }
         l = null;  // Make sure this gets GC'd
      }

      using (new OperationTimer("ArrayList of String")) {
         ArrayList a = new ArrayList();
         for (Int32 n = 0; n < count; n++) {
            a.Add("X");
            String x = (String) a[n];
         }
         a = null;  // Make sure this gets GC'd
      }
   }
}

// This is useful for doing operation performance timing.
internal sealed class OperationTimer : IDisposable {
   private Int64  m_startTime;
   private String m_text;
   private Int32  m_collectionCount;

   public OperationTimer(String text) {
      PrepareForOperation();

      m_text = text;
      m_collectionCount = GC.CollectionCount(0);
      
      // This should be the last statement in this 
      // method to keep timing as accurate as possible
      m_startTime = Stopwatch.GetTimestamp();    
   }

   public void Dispose() {
      Console.WriteLine("{0,6:###.00} seconds (GCs={1,3}) {2}",
         (Stopwatch.GetTimestamp() - m_startTime) / 
            (Double) Stopwatch.Frequency, 
         GC.CollectionCount(0) - m_collectionCount, m_text);
   }

   private static void PrepareForOperation() {
      GC.Collect();
      GC.WaitForPendingFinalizers();
      GC.Collect();
   }
}

Examine the output in terms of timing and garbage collections:

C:\Windows\MICROS~1.NET\FRAMEW~1\V20~1.507>performance
   .09 seconds (GCs=  0) List<int32>
  1.92 seconds (GCs= 28) ArrayList of Int32
   .39 seconds (GCs=  5) List<string>
   .44 seconds (GCs=  5) ArrayList of String

Another Example

Let's try to construct an example that consists of an object hierarchy with a Person class at the root and two descendant classes, Customer and Employee. The Person class provides an abstraction of those attributes that are common to every person. In our example, these shared attributes are represented by the Id, Name, and Status properties of the Person class. The Consumer and Employee classes also add their own specializations and behavior. More specifically, each of these classes also have a one to-many relationship with another class. A customer is associated with one or more orders, and an employee class contains references to one or more "child" employee objects that represent those employees that are managed by a specific person. We are going to see why using the ArrayList is not type-safe. Type safety is one of the main responsibilities of the CLR. This means we want our Person class to expose an interface for retrieving each of its items, and we want the types of those items to be type safe. That is, if we have a class of integers, we cannot pass it a string type, or else we would get a compiler error. Because Generics gives us a way to parameterize our types, we can use them in this example to parameterize the Person class, allowing it to accept a type parameter that will specify the types of elements collected by the Items property:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

public class Person<t> {
    public enum StatusType {
        Active = 1,
        Inactive = 2,
        IsNew = 3
    };

    private string _id;
    private string _name;
    private StatusType _status;
    private List<t> _items;

    public Person(String Id, String Name, StatusType Status) {
        this._id = Id;
        this._name = Name;
        this._status = Status;
        this._items = new List<t>();
    }

    public string Id {
        get { return this._id; }
    }

    public string Name {
        get { return this._name; }
    }

    public StatusType Status {
        get { return this._status; }
    }

    public T[] Items {
        get { return this._items.ToArray(); }
    }

    public void AddItem(T newItem) {
        this._items.Add(newItem);
    }
}

If we had an array of items, it would be internally managed by the ArrayList type, which is not type-safe. So we use the generic List collections (from the System.Collections.Generic namespace) which brings us to a greater level of type safety to this data member. We make sure that the Status property is changed to an enum type. Finally, we notice that the parameterization of the Person class enables the AddItem method to enforce type checking. Now each object type that gets added must match the type of the type parameter, T, to be considered valid:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

public class Customer : Person<order> {

    public Customer(String Id, String Name, 
       StatusType Status) : base(Id, Name, Status) {
    }
}

The Employee class:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

public class Employee : Person<employee> {

    public Employee(String Id, String Name, 
            StatusType Status) : base(Id, Name, Status) {
    }
}

The Order class:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace GenericPerson {
    public class Order {
        private DateTime _orderDate;
        private string _itemId;
        private string _description;

        public Order(DateTime OrderDate, string ItemId, string Description) {
            this._orderDate = OrderDate;
            this._itemId = ItemId;
            this._description = Description;
        }

        public DateTime OrderDate {
            get { return this._orderDate; }
        }

        public string ItemId {
            get { return this._itemId; }
        }

        public string Description {
            get { return this._description; }
        }
    }
}

Here is the main file of our generic Person:

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

using System.Collections;


    public class Program {
        public class GenericPersonTest {
            public GenericPersonTest() {
            }

            public List<customer> PopulateCustomerCollection() {
            List<customer> custColl = new List<customer>();
            Customer cust = new Customer("1", 
               "Ron Livingston", Customer.StatusType.Active);
            cust.AddItem(new Order(DateTime.Parse("10/01/2004"), 
                         "SWING-001", "Red Swingline Stapler"));
            cust.AddItem(new Order(DateTime.Parse("10/03/2004"), 
                         "XEROX-004", "Xerox Copier"));
            cust.AddItem(new Order(DateTime.Parse("10/07/2004"), 
                         "FAXPA-006", "Fax Paper"));

            custColl.Add(cust);

            cust = new Customer("2", "Milton Waddams", 
                                Customer.StatusType.Inactive);
            cust.AddItem(new Order(DateTime.Parse("11/04/2004"), 
                         "PRINT-061", "Printer"));
            cust.AddItem(new Order(DateTime.Parse("11/07/2004"), 
                         "3HOLE-024", "Three-hole punch"));
            cust.AddItem(new Order(DateTime.Parse("12/12/2004"), 
                         "DISKS-236", "CD-RW Disks"));

            custColl.Add(cust);

            cust = new Customer("3", "Bill Lumberg", 
                                Customer.StatusType.IsNew);
            cust.AddItem(new Order(DateTime.Parse("10/01/2004"), 
                         "WASTE-04", "Waste basket"));

            custColl.Add(cust);

            return custColl;
        }

        public List<employee> PopulateEmployeeCollection() {
            List<employee> empColl = new List<employee>();
            Employee emp = new Employee("1", 
              "Ron Livingston", Employee.StatusType.Active);
            empColl.Add(emp);

            emp = new Employee("2", 
              "Milton Waddams", Employee.StatusType.Inactive);
            empColl.Add(emp);

            emp = new Employee("3", "Bill Lumberg", 
                               Employee.StatusType.IsNew);
            emp.AddItem(new Employee("6", 
              "Samir Nagheenanajar", Employee.StatusType.Active));
            emp.AddItem(new Employee("7", 
              "Bob Porter", Employee.StatusType.Active));
            emp.AddItem(new Employee("8", 
              "Tom Smykowski", Employee.StatusType.Active));

            empColl.Add(emp);

            return empColl;
        }

        public void DisplayCustomers(List<customer> customers) {
            for (int custIdx = 0; custIdx < customers.Count; custIdx++) {
                Customer cust = customers[custIdx];
                Console.Out.WriteLine("Customer-> ID: {0}, " + 
                        "Name: {1}", cust.Id, cust.Name);

                Order[] orders = cust.Items;
                for (int orderIdx = 0; orderIdx < orders.Length; orderIdx++) {
                    Order ord = orders[orderIdx];
                    Console.Out.WriteLine("    Order-> " + 
                       "Date: {0}, Item: {1}, Desc: {2}", 
                       ord.OrderDate, ord.ItemId, ord.Description);
                }
            }
        }

        public void DisplayEmployees(List<employee> managers) {
            for (int mgrIdx = 0; mgrIdx < managers.Count; mgrIdx++) {
                Employee manager = managers[mgrIdx];
                Console.Out.WriteLine("Manager-> ID: {0}, " + 
                        "Name: {1}", manager.Id, manager.Name);

                for (int idx = 0; idx < manager.Items.Length; idx++) {
                    Employee emp = manager.Items[idx];
                    Console.Out.WriteLine("    Employee-> Id: {0}," + 
                            " Name: {1}", emp.Id, emp.Name);
                }
            }
        }

        public void RunPersonTest() {
            List<customer> custColl = PopulateCustomerCollection();
            List<employee> managerColl = PopulateEmployeeCollection();

            DisplayCustomers(custColl);
            DisplayEmployees(managerColl);

            Console.ReadKey();
        }
    }

    static void Main(string[] args) {
        GenericPersonTest personTest = new GenericPersonTest();
        personTest.RunPersonTest();

    }
}

Do you notice that collections are predominant in this technology? Well, we compile the class files on the .NET Framework (however, they are easily zipped together to build a solution using Visual Studio) using the target library switch and then reference all of those DLLs when we compile the main program. Here is the output:

c:\Windows\Microsoft.NET\Framework\v2.0.50727>csc /r:Order.dll /r:/employee.dll
/r:Person.dll /r:consumer.dll Program.cs
Microsoft (R) Visual C# 2005 Compiler version 8.00.50727.3521
for Microsoft (R) Windows (R) 2005 Framework version 2.0.50727
Copyright (C) Microsoft Corporation 2001-2005. All rights reserved.

c:\Windows\Microsoft.NET\Framework\v2.0.50727>Program
Customer-> ID: 1, Name: Joe Smith 
 Order-> Date: 10/1/2004 12:00:00 AM, Item: SWING-001, Desc: Red Swingline St
apler
    Order-> Date: 10/3/2004 12:00:00 AM, Item: XEROX-004, Desc: Xerox Copier
    Order-> Date: 10/7/2004 12:00:00 AM, Item: FAXPA-006, Desc: Fax Paper
Customer-> ID: 2, Name: Bi
    Order-> Date: 11/4/2004 12:00:00 AM, Item: PRINT-061, Desc: Printer
    Order-> Date: 11/7/2004 12:00:00 AM, Item: 3HOLE-024, Desc: Three-hole punch

    Order-> Date: 12/12/2004 12:00:00 AM, Item: DISKS-236, Desc: CD-RW Disks
Customer-> ID: 3, Name: Bill Lumberg
    Order-> Date: 10/1/2004 12:00:00 AM, Item: WASTE-04, Desc: Waste basket
Manager-> ID: 1, Name: Ron Livingston
Manager-> ID: 2, Name: Milton Waddams
Manager-> ID: 3, Name: Bill Lumberg
    Employee-> Id: 6, Name: Samir Nagheenanajar
    Employee-> Id: 7, Name: Bob Porter
    Employee-> Id: 8, Name: Tom Smykowski

All of that with stronger performance and less garbage collection, thank to Generics.

References

• .NET 2.0 Professional Generics by Tod Golding
• The CLR via C# by Jeffrey Richter