Templates


Up until now, we have only seen functions and ADTs (Abstract Data Types), that manipulate objects of fixed data types. Here, we'll show you how to abstract these functions and ADTs through the use of templates. As opposed to regular functions, which take actual objects as arguments, we shall see template functions that take data type(s) as argument(s). Then, we'll look at template classes.


1. Template Functions

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

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

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

double maximal(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 alternative is to declare the data type with typedef. That way, we only have to write the function once, and declare Item to be whatever data type we are planning to use.

place holder for the data type
         |
         v
typedef ___ Item; 
Item maximal(Item a, Item b) 
{
  if (a > b) 
    return a; 
  else 
    return b; 
} 

The only requirements needed for Items are that they have both the > (greater than) operator and copy constructor (if it is a class) defined.


Note: The reason we need a copy constructor, is that whenever an object is returned from a function, the compiler returns a copy of that object using the copy constructor.

The advantages of this approach are that we only have to write the function once and that the syntax being used is simple. The drawback of this approach is that we can only define one data type for Item.

An even better approach would be to write a template function. As in the typedef approach, we would only have to write the code once, but in addition, we could use it with different types of Items. The compiler will do the work of generating code for the function as many times as it is used with different data types. For example, if the program uses a template version of maximal() 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. This added advantage comes with a price--we have to learn a more cumbersome syntax.

1.1 Template Function Definition

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

For example:

template <class Item> 
Item maximal(Item a, Item b) 
{ 
  if (a > b) 
    return a; 
  else 
    return b; 
} 

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

When a template function is called, the compiler examines the types of the arguments and at that point determines the data type of Item.

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 << maximal(1000, 2000) << endl; // will print 2000

The maximal function is said to be instantiated with the data type Item set to int.

Similarly, we could do:

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


Important Note: 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:

1.3. Template Header Files and Implementation Files

In the header file for a template function:

In the implementation file:

Here is an example header file, implementation file and test program file:

To summarize, the advantage of a template function is that we have to write the function only once. In a single program, several different usages of a template function can result in several different versions of the function depending upon the underlying data types. (As we shall see, this is also true of template classes.)

Your Task

You are given the body of a swap function, which swaps the contents of two objects. (Recall, that in order for swap to do its designated task, you must pass the two objects by reference.)

Create a directory and download the following files:

First, compile the swap function implementation file swap.cpp along with the main file main.cpp, and run the program.

Then, convert the swap function into a template function, by doing the following:

  1. Copy the implementation file swap.cpp to swap.tem.
  2. Copy the header file swap.h to swap2.h.
  3. Change the header file swap2.h--remove the typedef declaration, add a template prefix to the swap function, and include the implementation file swap.tem at the end of the file.
  4. Remove the #include at the beginning of the implementation file swap.tem and add the template prefix to the swap function.
  5. Compile the main file main2.cpp and run the program.

2. Template Classes

A template class is a class that depends on an underlying data type in the same way a template function depend on an underlying data type.

2.1. Template Class Definition

As with template functions, we can replace the typedef version of a class definition. For example:

typedef ___ Item;
Class Bag
{
  ...
};

with the template version:

template <class Item> 
class Bag 
{ 
  ...
}; 

2.2. Functions for the Template Class

All member functions of a template class are dependent upon the Item type. Within the template class definition, the compiler knows about this dependency. Outside the template class definition (after the semicolon of the definition) some rules must be followed to tell the compiler about the dependency on the Item data type:

2.3. Header and Implementation Files

Like the template function case, the implementation of the functions must be present 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 using the #include directive.

2.4. Usage

To declare a Bag, you write the class name followed by the name of the data type for the template parameter. For example:

Bag<char> letters;  // template parameter is instantiated to char
Bag<double> scores; // template parameter is instantiated to double

Another example :

List <int> list;
list.insert(10); // insert node containing integer 10


Note: As opposed to a template function, where formal parameters types and actual arguments types had to match exactly, in the case of a template class member function, the compiler will try to type cast between different argument and parameter types. This is no different than what the compiler does for regular functions.

Here are an example header file, implementation file and test program file:

Your Task

You are given a complete class definition for a Stack class, along with an incomplete implementation of it. For reference see the stack web page. Your task consists of the following:

  1. Implement the missing pop() and isFull() member functions. Compile the stack implementation file along with the main file stacktest.cpp, and run the program.
  2. "Templatize" the Stack class:
    1. Copy the implementation file stack.cpp to stack.tem.
    2. Copy the header file stack.h to stack2.h.
    3. Change the header file stack2.h--remove the typedef declaration, add a template prefix to the Stack class, and include the implementation file stack.tem at the end of the file.
    4. Remove the second include (#include "stack.h") from the beginning of the implementation file stack.tem, add the template prefix to all member functions, and change Stack:: to Stack<StackElementT>:: throughout.
  3. Compile the main file stacktest2.cpp and run the program.

    Here are the header file, implementation file and test programs for the stack:


    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.