C++ Annotations Version 4.0.0

Chapter 14: Templates

We're always interested in getting feedback. E-mail us if you like this guide, if you think that important material is omitted, if you encounter errors in the code examples or in the documentation, if you find any typos, or generally just if you feel like e-mailing. Mail to Frank Brokken or use an e-mail form. Please state the concerned document version, found in the title. If you're interested in a printable PostScript copy, use the form, or better yet, pick up your own copy by ftp from ftp.icce.rug.nl/pub/http.

Most modern C++ compilers support a `super-macro-mechanism' which allows programmers to define generic functions or classes, based on a hypothetical argument or other entity. The generic functions or classes become concrete code once their definitions are used with real entities. The generic definitions of functions or classes are called templates.

In this chapter we shall examine template functions and template classes.

14.1: Template functions

The definition of a template function is very similar to the definition of a concrete function, except for the fact that the arguments to the function are named in a symbolic way. This is best illustrated with an example:

template <class T> void swap(T &a, T &b) { T tmp = a; a = b; b = tmp; }

In this example a template function swap() is defined, which acts on any type as long as variables (or objects) of that type can be assigned to each other and can be initialized by one another. The generic type which is used in the function swap() is called here T, as given in the first line of the code fragment.

The code of the function performs the following tasks:

First, a variable of type T is created (this is tmp) and initialized with the argument a.
Second, the variables which are referred to by a and b are swapped, using tmp as an intermediate.

The actual references a and b could refer to ints, doubles or to any other type. Note that the definition of a template function is similar to a #define in the sense that the template function is not yet code, but it will result in code once it is used.

As an example of the usage of the above template function, consider the following code fragment (we use the class Person from section 5 as illustration):

int main() { int a = 3, b = 16; double d = 3.14, e = 2.17; Person k("Karel", "Rietveldlaan 37", "5426044"), f("Frank", "Oostumerweg 17", "4032223"); swap(a, b); printf("a = %d, b = %d\n", a, b); swap(d, e); printf("d = %lf, e = %lf\n", d, e); swap(k, f); printf("k's name = %s, f's name = %s\n", k.getname(), f.getname()); return (0); }

Once the C++ compiler encounters the usage of the template function swap(), concrete code is generated. This means that three functions are created, one to handle ints, one to handle doubles and one to handle Persons. The compiler generates mangled names (see also section 2.4.9) to distinguish between these functions. E.g., internally the functions may be named swap_int_int(), swap_double_double() and swap_Person_Person().

It should furthermore be noted that, as far as the class Person is concerned, the definition of swap() requires a copy constructor and an overloaded assignment operator.

The fact that the compiler only generates concrete code once a template function is used, has an important consequence. The definition of a template function can never be collected in a run-time library. Rather, a template should be regarded as a kind of declaration, and should be given in a file which has a comparable function as a header file.

14.2: Template classes

The `super-macro-mechanism' which is offered by templates can be used to define generic classes, which are intended to handle any type of entity. Typically, template classes are container classes and represent arrays, lists, stacks or trees, similar to the container classes described in chapter 15.

14.2.1: A template class: Array

As an example we present here a template class Array, which can be used to store arrays of any kind of element:

#include <stdio.h> #include <stdlib.h> template<class T> class Array { public: // constructors, destructors and such virtual ~Array(void) { delete [] data; } Array(int sz = 10) { init(sz); } Array(Array<T> const &other); Array<T> const &operator=(Array<T> const &other); // interface int size() const; T &operator[](int index); private: // data int n; T *data; // initializer void init(int sz); }; template <class T> void Array<T>::init(int sz) { if (sz < 1) { fprintf(stderr, "Array: cannot create array of size < 1\n" " requested: %d\n", sz); exit(1); } n = sz; data = new T[n]; } template <class T> Array<T>::Array(Array<T> const &other) { n = other.n; data = new T[n]; for (register int i = 0; i < n; i++) data[i] = other.data[i]; } template <class T> Array<T> const &Array<T>::operator=(Array<T> const &other) { if (this != &other) { delete []data; n = other.n; data = new T[n]; for (register int i = 0; i < n; i++) data[i] = other.data[i]; } return (*this); } template <class T> int Array<T>::size() const { return (n); } template <class T> T &Array<T>::operator[](int index) { if (index < 0 || index >= n) { fprintf(stderr, "Array: index out of bounds, must be between" " 0 and %d\n" " requested was: %d\n", n - 1, index); exit(1); } return (data[index]); }

Concerning this definition we remark:

The definition of the class starts with
template <class T>
This is similar to the definition of a template function: this line holds the symbolic name T, referring to the type which will be handled by the class.
In the class definition, all functions which have an Array as their argument (e.g., the copy constructor) refer to this argument as an Array<T>.
In the function definitions, the class name is referred to as Array<T>. The reason for this is the following: similar to name mangling in template functions, the compiler will modify the class name Array to a new name, when the class is concretely used. The symbolic name T will then become a part of the new class name.

Concerning the statements in the template we remark:

The template class Array uses two data members: a pointer to an allocated array (data) and the size of the array (n).

The class contains a copy constructor, (virtual) destructor and overloaded assignment function, since it addresses allocated memory.

Note the statement delete [] data in the destructor and overloaded assignment. This statement makes sure that, when data points to an array of objects, the destructor for the objects is called prior to the deallocation of the array itself.

The statement data[i] = other.data[i] in the overloaded assignment copies the data from another Array. This statement may actually copy memory byte by byte, or activate an overloaded assignment operator when the stored data is, e.g., a Person (see section 5).

Concerning the template class Array and in general all template classes, we have to remark that the template itself must be known to the compiler at compile-time. This usually means that the definition of the template class must be known in the source file in which the template is used to instantiate code. Usually this is realized by defining the template in a special header file, e.g., array.t (note the extension .t, in the template defining file array.t which is a style-convention distinguishing declaration header files from template header files).

By including the template header file in the source file in which the template is used, the compiler is able to create the neccesary code instantiating one or more member functions or objects of the template.

14.2.2: Using the Array class

The template class Array is used as illustrated in the following example:

#include <stdio.h> #include "array.t" #define PI 3.1415 int main() { Array<int> intarr; for (register int i = 0; i < intarr.size(); i++) intarr[i] = i << 2; Array<double> doublearr; for (i = 0; i < doublearr.size(); i++) doublearr[i] = PI * (i + 1); for (i = 0; i < intarr.size(); i++) printf("intarr[%d] : %d\n" "doublearr[%d]: %g\n", i, intarr[i], i, doublearr[i]); return (0); }

Note that the actual type of the array must be supplied when defining an object of the template class.

The class can, of course, be used with any type (or class) as long as arrays of the type can be allocated and entities of the type can be assigned. For a class such as Person this means that a default constructor and overloaded assignment function are needed. An illustration follows:

int main() { Array<Person> staff(2); // array of two persons Person one, two; . // code assigning names and . // addresses and phone numbers . // not covered in this example staff[0] = one; staff[1] = two; printf("%s\n%s\n", staff[0].getname(), staff[1].getname()); return (0); }

Since the above array staff consists of Persons, the Person's interface functions such as getname() can be called for elements in the array.

14.3: Templates and Exceptions

14.4: Evaluation of template classes

In this chapter and in chapter 15 we have seen two approaches to the construction of container classes.

The Storable/Storage approach from chapter 15 (see section 15) defines a `storable' prototype with a pure virtual function duplicate(). During the storage, in the class Storage, this function is called to duplicate an object.
This approach imposes the need for a duplicating function for each object which is derived from Storable so that it may placed in a Storage.
The template approach discussed in this chapter, using the template class Array, poses no such restrictions when it is used. I.e., following a definition of an Array object, to hold say Persons, as in:
Array<Person> staff;
the array can be used, without modifying or adapting the class Person.

The above comparison suggests that templates are a much better approach to container classes.

There is, however, one disadvantage: whenever a template class with a given type (Person, Vehicle or whatever) is used, the compiler must construct a new `real' class, each with its own mangled name (say ArrayPerson, ArrayVehicle).

A function such as init(), which is defined in the template class Array, then occurs twice in a program: once as ArrayPerson::init() and once as ArrayVehicle::init(). Of course, this holds true not only for init() but for all member functions of a template class.

In contrast, the Storable/Storage approach from chapter 15 requires only two new functions: one duplicator for a Person and one for a Vehicle. The code of the container class itself occurs only once in a program.

Terefore, we conclude the following:

When a program uses only one container class, the template approach is preferable: it is easier to use and requires no special precautions or conversions as far as the contained class is concerned.
When a program uses several instances of a container class, the Storable/Storage approach is preferable: it prevents needless code duplication, though it does require special adaptations of the contained class.