6.1 Templates


A number of common programming situations require the same class structure to be applied to different data types. Examples of several such situations in user interface systems are the following:
queue class
list class
set class
In each case the same basic algorithms and supporting data structures are needed. What varies among uses of the class is the type of the data being manipulated.

A good mechanisms for dealing with these situations should avoid repetitive programming and preserve the type safety normally expect of a well designed class. Avoiding repetitive code means that it should not be necessary to implement as distinct classes MouseEventQueue and CharacterQueue where the only difference between them is the type of the data contained in the queue. Preserving the type safety means that we do not want to avoid the repetitive code by writing an overly general (type-dumb) class. For example, it is possible to implement a single Queue class that manipulates "void*" types. This design is overly general because it allows anything to be put into the queue (e.g., MouseEvents in a CharacterQueue).

A template is a parameterized class whose parameter denotes the varying type of data. The syntax in C++ to introduce a template for the queue class is as follows:

   template < class QueueItem > class Queue { ... }
Enclosed in the angle brackets after the keyword "template" is the template parameter. In this example the template parameter, QueueItem, is a class. For a Queue, QueueItem is intended to denote the type of the items that the Queue will hold. The template parameter may be used in the parameterized class (Queue) in one or more of the following ways: These uses of the template parameter are shown in the following expansion of the Queue class:
   template <class QueueItem> class Queue {

   private:

      QueueItem buffer[100];
      int head, tail, count;

    public:
                Queue();
      void      Insert(QueueItem item);
      QueueItem Remove();
               ~Queue();

   };
In this code QueueItem is first used to define the type of the buffer array. This array is used to hold the elements that are currently in the queue. The parameter of the Insert method is defined as a QueueItem, matching the declaration of the buffer array where the input value will be stored. Finally, the result returned by the Remove method is also of type QueueItem since this is the type of data extracted from the buffer array.

A parameterized type (template) can be used to create a new class by instantiating the template with an appropriate parameter. The template can be used to create a new class in one of two ways. The first way directly creates an object as shown here:

    Queue<int> intQueue;	       // a queue of integers object
In this case the object intQueue is defined as an instance of the parameterized typed Queue where the parameter is taken as an "int" type. The second way uses the typedef to define a type (class) name as shown here:
    typedef Queue<int> IntegerQueue;  // a class for a queue of integers
    IntegerQueue intQueue;

In either case an object is created that acts like a queue of integers. This object can be manipulated in the usual ways. For example the queue of integers can be tested as follows:
	intQueue.Insert(100);		// add 100
        intQueue.Insert(200);		// add 200
        int x = intQueue.Remove();	// remove 100
	intQueue.Insert(300);		// queue now has (200,300)
        int x = intQueue.Size();	// size is 2

Notice that there is no difference in the way the intQueue objects is accessed. An object created from an instantitated template is indistinugishable from an object created from a non-parameterized class.

To complete the implementation of a template class each of its methods must be defined. Each template method may be part of several classes. For example the Queue's Remove method may be in the class Queue<int> and in the class Queue<char> and in the class Queue<floatgt>. To prevent confusion the definition of each method must carry a preamble that allows it to be associated with the specific template instantiation to which it belongs. This leads to the (somewhat wordy) syntax:


 template<class QueueItem>           Queue<QueueItem>::Queue()
                                         { ... }
 template<class QueueItem> void      Queue<QueueItem>::Insert(QueueItem item) 
                                         { ... }
 template<class QueueItem> QueueItem Queue<QueueItem>::Remove()           
                                         { ... }
 template<class QueueItem> int       Queue<QueueItem>::Size()
                                         { ... }
 template<class QueueItem>           Queue<QueueItem>::~Queue()
                                         { ... }

Each method definition is preceeded by a template specification ("template< class QueueItem>). In addition, the class name contains the template syntax (Queue<QueueItem>::). Note that in the case of the Remove method, the return type comes after the initial template specification and before the class name.

The complete code for the parameterized Queue class is shown here:

   template <class QueueItem> class Queue {
   private:
      QueueItem buffer[100];
      int head, tail, count;
    public:
                Queue();
      void      Insert(QueueItem item);
      QueueItem Remove(); 
      int       Size();
               ~Queue();
   };

   template <class QueueItem>           
      Queue<QueueItem>::Queue() : count(0), head(0), tail(0) {}

   template <class QueueItem> 
      void Queue<QueueItem>::Insert(QueueItem item) {
             assert(count <100);
             buffer[tail] = item;
             tail = (tail + 1)% 100;
             count++;
      }

   template <class QueueItem> 
      QueueItem Queue<QueueItem>::Remove() {
            assert(count > 0);
            int val = head;
            head = (head + 1)%100;
            count--;
            return buffer[val];
      }

   template <class QueueItem> 
      int Queue<QueueItem>::Size() { return count; }

   template <class QueueItem>           
      Queue<QueueItem>::~Queue() {}


Templates also differ from non-parameterized classes in where the method definitions are placed. In non-parameterized classes, the method definitions are put in a code (.cc or .C of .cpp) file. However, for a parameterized class the method definitions are placed in the header (.h) file itself. This is necessary so that when the compiler is asked to elaborate a template (e.g, by seeing a declaration of the form Queue*ltint>), it need only examine the header file (that has been referenced in a #include statement) to find all of the information that it needs to fully understand how to elaborate the template and generate the code for the required class.

Exercises

  1. Write a program that creates and manipulates two queues of type Queue<int>. Declare one of the queues directly as a Queue<int> and declare the other queue using a typedef.

  2. Use the code developed in question 1 to determine if you can assign a queue to a queue? Does this do what you expect?

  3. Write a program that creates and manipulates two queues of type Queue<Location>. Declare one of the queues directly as a Queue<Location> and declare the other queue using a typedef.

  4. Compile the following two declarations. Which one has a syntax error?
    	Queue<Queue<int>>
            Queue <Queue <int> >
    

  5. Draw a picture showing what structure is defined by the declaration in question 4.

  6. Write a test program that declares and manipulates the queue structure defined in question 4.

  7. Shown below is the code for an IntArray class. Create a template version of this class and write a program to test your template.
    
      class IntArray {
      private:
         int array[100];
      public:
              Array();
         int& At(int i);
              ~Array();
      };
    
      IntArray::IntArray() {};
      int& IntArray::At(int i)
               {assert(0<i && i < 100);
                return array[i];
    	   }
      IntArray::~IntArray() {}
    

  8. Using your Array template, write a test program to create and manipulate a two dimensional integer array as follows: typedef Array< Array<int> > Matrix. How do you access elements in this two dimensional array?

  9. Write a test program that declares and manipulates an array of queues.

  10. Write a test program that declares and manipulates a queue of arrays.

Last Updated: November 7, 1995 / kafura@cs.vt.edu