Templates


Until now, we have only seen functions and data structures that deal with fixed data types. Here, we'll show you how to generalize these functions and data structures through the use of templates. First, we'll look at template functions, then template classes.


1. Template Functions

Suppose we want to write a function that finds the maximum of two things. To find the maximum of two integers we would write:

int maximum(int a, int b) 
{
  if (a > b) 
    return a; 
  else 
    return b; 
} 

and to find the maximum of two doubles we would write:

double maximum(double a, double b) 
{
 if (a > b) 
   return a; 
 else 
   return b; 
} 

and so on. You can imagine that we would have to write a separate function for every data type (chars, strings, dates, etc.), but notice that the body of each function is exactly the same!!!

A better approach would be to write a template function. We can write the code once and use it with different types of things.

1.1 Template Function Definition

The definition of a template function depends on an underlying data type. For example:

template <class Type> 
Type maximum(Type a, Type b) 
{ 
  if (a > b) 
    return a; 
  else 
    return b; 
} 

The first line is the template prefix, which tells the compiler that Type is a data type that will be filled in later. The "unspecified type" Type is called the template parameter.


Note: This template function requires that its parameters can be compared with greater than (>).

1.2 Using Template Functions

Template functions are used (called) in exactly the same way as regular functions.

For example, if we want to output the maximum of the integers 1000 and 2000, we would write:

cout << maximum(1000, 2000) << endl; // will print 2000

The maximum function is said to be instantiated with Type set to int.

Similarly, we could do:

cout << maximum('a', 'z') << endl; // will print 'z'
string s1("foo");
string s2("bar");
cout << maximum(s1, s2) << endl; // will print "foo" 


Note: The compiler will do the work of generating a new version of the function as many times as it is used with different data types. For example, if the program uses a template version of maximum() to find the maximum of two integers and two doubles, the compiler will generate code for two versions of the function, one for ints and one for doubles.

It is only when the function is instantiated (i.e., by code that calls the function) that the compiler compiles a certain version of the template function, using the specified type.


Requirements:


2. Template Classes

A template class is a class that depends on an underlying data type just like a template function.

2.1. Template Class Definition

The class definition of a template class starts with a template prefix:

template <class Type> 
class SomeClass
{ 
  ...
}; 

Inside the class, the template parameter Type can be used, but won't be filled in until the template class is instantiated.

As an example, let's look at a template class, Array, which implements a resizable array. The class definition is in file array.h.

2.2. Template Class Method Definitions

The methods for our template Array class are available in file array.tem.

In the method definitions, some rules must be followed to tell the compiler about the dependency on the template parameter:


Note: Our implementation of the Array class relies on being able to assign items to one another.

2.3. Usage

To create a resizable array, we now just need to instantiate the class with a data type. For example:

Array<int> iarray;  // array of integers
Array<string> sarray; // array of strings

We can then use them:

iarray.resize(10);
iarray[6] = 19;
sarray.resize(5);
sarray[2] = string("foo");

The file arraytest.cpp instantiates our Array class with a couple types of elements.

2.4. Header and Implementation Files

For non-templates (functions or classes) stored in a module, we organized them as follows:

main.cpp              mod.h                 mod.cpp
-------------------   --------------------  --------------------
|#include "mod.h" |   |...               |  |#include "mod.h"  |
|...              |   |                  |  |...               |
-------------------   --------------------  --------------------

And we compiled the code that uses the module (here, main.cpp) together with the code that implements the module, mod.cpp (likewise we could just link their object files together).

With templates (functions or classes) stored in a module, the implementation should be included in the header file. It is common practice to put the function implementations in a separate implementation file, and then include this file in the header file.

main.cpp              mod.h                 mod.tem
-------------------   --------------------  --------------------
|#include "mod.h" |   |...               |  |...               |
|...              |   |#include "mod.tem"|  |                  |
-------------------   --------------------  --------------------

To compile the code, we just compile the code that uses the module (here, main.cpp) since the entire template code gets included.


Note: Template functions or classes cannot be compiled until they are instantiated (i.e., the template parameter is filled in). Thus, a module with a template cannot be compiled by itself.

Compile the array test program and run it.


Exercise

You are given a List class (list.h and list.cpp) that represents a linked list of integers.

  1. Complete the methods insertAtBeginning() and removeFromEnd(). Then compile the list module with the main program listtest.cpp to ensure it works.

  2. Change the linked list into a template class:
    1. Rename the implementation file list.cpp to list.tem.

    2. In list.h:
      1. Add the template prefix "template <class Item>" to the class definition.
      2. Replace uses of int (as the type of items) with the template parameter Item.
      3. Add #include "list.tem" after the class definition.

    3. In list.tem:
      1. Remove the #include "list.h".
      2. Add the template prefix "template <class Item>" to all method definitions.
      3. Change all "List::" to "List<Item>::".
      4. Replace uses of int (as the type of items) with the template parameter Item.

    4. Change the main program to instantiate a List with type int. Compile the new program and run it.


A few final notes


BU CAS CS - Templates
This page created by Jonathan Alon <jalon@cs.bu.edu>.
Material adapted from the textbook "Data Structures and Other Objects Using C++", by Main and Savitch.
Modified by Robert I. Pitts <rip@bu.edu>