course of C++ programming language

lecture 14, 15: templates

Introduction

Templates provide direct support for generic programming - programming using types as parameters. The C++ template mechanism allows a type to be a parameter in the definition of a class or a function. A template depends only on the properties that it actually uses from its parameter types and does not require different types used as arguments to be explicitly related. In particular, the argument types used for a template need not be from a single inheritance hierarchy.

Using templates, it is possible to create generic functions and classes. In a generic function or class, the type of data upon which the function or class operates is specified as a parameter. Thus, you can use one function or class with several different types of data without having to explicitly recode specific versions for each data type.

Generic functions

A generic function defines a general set of operations that will be applied to various types of data. The type of data that the function will operate upon is passed to it as a parameter. Through a generic function, a single general procedure can be applied to a wide range of data.

By creating a generic function, you can define the nature of the algorithm, independent of any data. Once you have done this, the compiler will automatically generate the correct code for the type of data that is actually used when you execute the function. In essence, when you create a generic function you are creating a function that can automatically overload itself.

A generic function is created using the keyword template. The normal meaning of the word template accurately reflects its use in C++. It is used to create a template (or framework) that describes what a function will do, leaving it to the compiler to fill in the details as needed.

template <class X> void swapargs (X &a, X &b) { X temp; temp = a; a = b; b = temp; }

Here, X is a placeholder name for a data type used by the function. This name may be used within the function definition. However, it is only a placeholder that the compiler will automatically replace with an actual data type when it creates a specific version of the function. Although the use of the keyword class to specify a generic type in a template declaration is traditional, you may also use the keyword typename.

int main () { int i=10, j=20; double x=10.1, y=23.3; string a="abc", b="xyz"; cout << "Original i, j: " << i << ' ' << j << endl; cout << "Original x, y: " << x << ' ' << y << endl; cout << "Original a, b: " << a << ' ' << b << endl; swapargs(i, j); // swap integers swapargs(x, y); // swap floats swapargs(a, b); // swap strings cout << "Swapped i, j: " << i << ' ' << j << endl; cout << "Swapped x, y: " << x << ' ' << y << endl; cout << "Swapped a, b: " << a << ' ' << b << endl; return 0; }

The line template <class X> void swapargs (X &a, X &b) tells the compiler two things: that a template is being created and that a generic definition is beginning. Here, X is a generic type that is used as a placeholder. After the template portion, the function swapargs() is declared, using X as the data type of the values that will be swapped. In main(), the swapargs() function is called using three different types of data: ints, doubles, and strings. Because swapargs() is a generic function, the compiler automatically creates three versions of swapargs(): one that will exchange integer values, one that will exchange floating-point values, and one that will swap sequences of characters.

A generic function (that is, a function definition preceded by a template statement) is also called a template function. Both terms will be used interchangeably in this book. When the compiler creates a specific version of this function, it is said to have created a specialization. This is also called a generated function. The act of generating a function is referred to as instantiating it. Put differently, a generated function is a specific instance of a template function.

You can define more than one generic data type in the template statement by using a comma-separated list.

template <class X, class Y> X poly (X x, Y coef[], unsigned int d) { X temp = coef[d]; while (d--) temp = x*temp+coef[d]; return temp; }

When you create a template function, you are, in essence, allowing the compiler to generate as many different versions of that function as are necessary for handling the various ways that your program calls the function.

Explicitly overloading a generic function

Even though a generic function overloads itself as needed, you can explicitly overload one, too. This is formally called explicit specialization. If you overload a generic function, that overloaded function overrides (or hides) the generic function relative to that specific version.

template <class T> void swapargs (T &a, T &b) { T temp; temp = a; a = b; b = temp; } // this overrides the generic version of swapargs() for ints void swapargs (int &a, int &b) { a ^= b, b ^= a, a ^= b; }

Recently, a new-style syntax was introduced to denote the explicit specialization of a function. This new method uses the template keyword. For example, using the new-style specialization syntax, the overloaded swapargs() function from the preceding program looks like this.

// use new-style specialization syntax template <> void swapargs<int> (int &a, int &b) { a ^= b, b ^= a, a ^= b; }

Explicit specialization of a template allows you to tailor a version of a generic function to accommodate a unique situation-perhaps to take advantage of some performance boost that applies to only one type of data, for example. However, as a general rule, if you need to have different versions of a function for different data types, you should use overloaded functions rather than templates.

Overloading a function template

In addition to creating explicit, overloaded versions of a generic function, you can also overload the template specification itself. To do so, simply create another version of the template that differs from any others in its parameter list.

// the first version of f() template template <class X> void f (X a) { cout << "inside f(X)" << endl; } // the second version of f() template template <class X, class Y> void f (X a, Y b) { cout << "inside f(X,Y)" << endl; }

You can mix standard parameters with generic type parameters in a template function. These nongeneric parameters work just like they do with any other function.

// the third version of f() template template <class X> void f (X a, int c, int d) { cout << "inside f(X,int,int)" << endl; }

The mixing of generic and nongeneric parameters causes no trouble and is, indeed, both common and useful.

Default template parameters

You can give template parameters default values. For example, you might want to say that the default container for your Set is a std::vector. The template class definition would look like this.

template <class Type, class Container=std::vector<Type> > class Set { // ... };

You can use the type Type from the first template parameter as the argument to the std::vector template in the default value for the second template parameter.

C++ syntax requires that you do not repeat the default value in the template header line for method definitions.

Set<double, deque<double> > a; Set<int> b;

With this default parameter, clients can now instantiate a grid with or without specifying an underlying container.

Source code organization

Even if you create non-inline function definitions, you'll usually want to put all declarations and definitions for a template into a header file. This may seem to violate the normal header file rule of "Don't put in anything that allocates storage" (which prevents multiple definition errors at link time), but template definitions are special. Anything preceded by template<> means the compiler won't allocate storage for it at that point, but will instead wait until it's told to (by a template instantiation), and that somewhere in the compiler and linker there's a mechanism for removing multiple definitions of an identical template. So you'll almost always put the entire template declaration and definition in the header file, for ease of use.

Consider a simple template:

// msg.cpp # include <iostream> template <class T> void msg (const T &m) { std::cerr << m << endl; }

We can include msg.cpp wherever msg() is needed. For example:

// user1.cpp # include "msg.cpp" /* use msg() */
// user2.cpp # include "msg.cpp" /* use msg() */

That is, the definition of msg() and all declarations it depends on are included in several different compilation units. It is up to the compiler to generate code when needed (only) and to optimize the process of reading redundant definitions. This strategy treats template functions the same way as inline functions.

One obvious problem with this is that everything on which the definition of msg() depends is added to each file using msg(), thus increasing the amount of information that the compiler must process. Another problem is that users may accidentally come to depend on declarations included only for the benefit of the definition of msg(). This danger can be minimized by using namespaces, by avoiding macros, and generally by reducing the amount of information included.

The separate compilation strategy is the logical conclusion of this line of thinking: if the template definition isn't included in the user code, none of its dependencies can affect that code. Thus we split the original msg.cpp into two files:

// msg.h template <class T> void msg (const T &m);
// msg.cpp # include <iostream> # include "msg.h" export template <class T> void msg (const T &m) { std::cerr << m << endl; }

The file msg.cpp now holds all of the information needed to define msg(), and msg.h holds only what is needed to call it. A user includes only the declaration (the interface):

// user1.cpp # include "msg.h" /* use msg() */
// user2.cpp # include "msg.h" /* use msg() */

This strategy treats template functions the same way it does non-inline functions. The definition (in msg.cpp) is compiled separately, and it is up to the implementation to find the definition of msg() when needed. This strategy also puts a burden on the implementation. Instead of having to filter out redundant copies of a template definition, the implementation must find the unique definition when needed.

Note that to be accessible from other compilation units, a template definition must be explicitly declared export. This can be done by adding export to the definition or to a preceding declaration. Otherwise, the definition must be in scope wherever the template is used.

Generic classes

In addition to generic functions, you can also define a generic class. When you do this, you create a class that defines all the algorithms used by that class; however, the actual type of the data being manipulated will be specified as a parameter when objects of that class are created.

Generic classes are useful when a class uses logic that can be generalized. For example, the same algorithms that maintain a queue of integers will also work for a queue of characters, and the same mechanism that maintains a linked list of mailing addresses will also maintain a linked list of auto part information. When you create a generic class, it can perform the operation you define, such as maintaining a queue or a linked list, for any type of data. The compiler will automatically generate the correct type of object, based upon the type you specify when the object is created.

In the following program, the Stack class is a generic class. Thus, it can be used to store objects of any type. In this example, a character stack and a floating-point stack are created, but any data type can be used.

template <class StackType> class Stack { public: static const int SIZE; protected: StackType stack[SIZE]; // holds the stack int tos; // index of top-of-stack public: Stack() { tos = 0; } // initialize stack void push(StackType ob); // push object on stack StackType pop(); // pop object from stack // ... };

As you can see, the declaration of a generic class is similar to that of a generic function. The actual type of data stored by the stack is generic in the class declaration. It is not until an object of the stack is declared that the actual data type is determined.

int main () { Stack<char> sc1, sc2; sc1.push('a'); sc1.push('b'); sc2.push('c'); sc1.pop(); // ... Stack<double> sd1, sd2; sd1.push(-1.0); sd1.push(3.14); sd2.push(2.72); sd1.pop(); // ... };

When a specific instance of Stack is declared, the compiler automatically generates all the functions and variables necessary for handling the actual data. In this example, two different types of stacks are declared: Stack<char> and Stack<double>.

Template parameters

A template can take type parameters, parameters of ordinary types such as int and template parameters. Naturally, a template can take several parameters.

template<class T1, class T2> class Pair { /* ... */ }; template<class T, int S> class Queue { /* ... */ }; template<class T, T def_val> class Cont { /* ... */ };

Non-type parameters are restricted to integers, pointers, or references. Other types, such as float, are not allowed. The arguments that you pass to a non-type parameter must consist of either an integer constant, or a pointer or reference to a global function or object. Thus, non-type parameters should themselves be thought of as constants, since their values cannot be changed.

Using default arguments with template classes

A template class can have a default argument associated with a generic type.

template<class X=int> class MyClass1 { /* ... */ }; template<class T, class Container=Stack<T> > class MyClass2 { /* ... */ };

It is also permissible for non-type arguments to take default arguments. The default value is used when no explicit value is specified when the class is instantiated. Default arguments for non-type parameters are specified using the same syntax as default arguments for function parameters.

Explicit class specializations

As with template functions, you can create an explicit specialization of a generic class. To do so, use the template<> construct, which works the same as it does for explicit function specializations.

template<class T> class MyClass { /* ... */ }; template<> class MyClass<int> { /* ... */ };

One specialization is more specialized than another if every argument list that matches its specialization pattern also matches the other, but not vice versa.

template<class T> class MyVector { /* ... */ }; // general template<class T> class MyVector<T*> { /* ... */ }; // specialized for any pointer template<> class MyVector<void*> { /* ... */ }; // specialized for void*

Every type can be used as a template argument for the most general MyVector, but only pointers can be used for MyVector<T*> and only void*s can be used for MyVector<void*>.

References
  1. B.Stroustrup: The C++ programming language. Third edition.
    Section 13: templates; pp. 327-352.
  2. H. Schildt: C++: the complete reference. Third edition.
    Section 18: templates; pp. 461-487.
  3. B.Eckel: Thinking in C++. Second edition.
    Section 16: introduction to templates; pp. 689-743.