Chapter 13: Generics and Templates

OVERVIEW

Templates (also known as generics) allow code to be written in such a way that the same program can be used for different data types. Consider for example a C linked-list program that is written to hold a list of integers. If you wanted to store a list of, say, floating point types, you'd need to create a new program for that. And if you wanted to store a list of strings, you'd need to create yet another version of the same program. All of these different versions of the linked-list program would have a great deal in common, since, after all, all linked lists possess the same fundamental structure: you have a list of linked nodes, and, at the least, each node must hold one element and, at the same time, point to the next node.

Ordinarily, this problem also exists with C++ programs. If you were to create, say, a linked-list program in C++ for storing integers, you would not be able to use the same program for storing strings. Java, on the other hand, stands at the other extreme: You could easily write a Java linked-list program that would be able hold items of any type. In fact, within the same linked list, you could have the first node hold an integer, the second node hold a string, and so on. That's because what would actually be stored in a node would be a reference to an Object, the root class of all objects in Java, and each such reference could point to a data item of a different type. But, unfortunately, as the reader will see from the examples in this chapter, this behavior of Java comes at a price: When you want to extract an item from a container, you have to remember to cast it back to the type that was actually stored in the container. Forgetting to cast or using an incorrect cast can result in run-time errors.

Modern thinking is that both these extremes of language behavior—container classes that work for only one data type or that work for all data types—lead to programming inefficiencies. The former because you have to create a new container class for each separate data type and the latter because of the casts that are needed for the retrieval of the correct data type.

To get around these limitations, we have templates in C++ and generics in Java. A templatized program (or a generic program) can be a class or a method that is parameterized by a variable that can be instantiated to different types. For example, an ordinary linked-list program in C++ may look like

     class LinkedList {         struct Node {             Node* next;             int val;         };           Node* head;     public:         // public interface of the class         ....         ....     }; 

The individual nodes of the linked list will be instances of the nested class, a struct named Node. Note that since the data member val of the struct Node is defined to be of type int, this linked list will only be able to hold integers. Now compare this with the following templatized version:

     template<class T> class LinkedList {         struct Node {             Node* next;             T val;         };         Node* head;     public:         // public interface of the class         ....         ....     }; 

Note how the header of the class has been parameterized by incorporating the variable T and how the type of the data member val inside the nested class Node has been declared to be of type T. With this new definition, LinkedList<int> would do exactly the same as our previous LinkedList class. But now we can use the same program to create a LinkedList<double> class for storing a list of doubles, a LinkedList<string> class for storing a list of strings, and so on.

Let's now consider Java. An ordinary linked list class in Java may have its header and the beginning section look like this:

     class LinkedList {         class Node {             Object element;             Node next;         }         Node head;         // the public interface of the class         ....         ....     } 

The individual nodes of the linked list will be of type Node, which is a nested class above. Each node will store an item of the list in the data member element. Since this data member is of type Object, we have the freedom to store any class-type object in the different nodes of the list. But, as mentioned earlier, the price to pay for this flexibility is that we must remember to cast the item down to its correct type when it is retrieved from the list. Alternatively, we can use the parameterized version of this class shown below that lets us use the same program for linked lists of different data types and, at the same time, does away with the need for casting at the time of retrieval:

     class LinkedList<T> {         class Node {             T element;             Node next;         }         Node head;         // the public interface of the class         ....         ....     } 

With the parameterization^[1] of the class header, now the list items stored in the individual nodes will be of type T. This new parameterized class could now be used as LinkedList<Integer> to store items of type Integer, LinkedList<String> to store items of type String, and so on.

In the rest of this chapter, we will first present the class and function parameterization in C++. Class and function parameterizations are integral parts of the C++ language. In fact, as a programming language, C++ derives much of its power from such parameterizations.

Next, we will show how to write parameterized classes and methods in Java. Although such parameterizations are not yet features of the language as officially released (and therefore should not be used for writing portable Java code at this time), there is much educational value in seeing that Java can be endowed with the same sort of parameterizations that one finds in C++.

^[1]The words templatization and parameterization will be used interchangeably in this chapter. Same with the words templatized and parameterized.