Generalizing Types with Templates

A template makes the element type a parameter, so one definition such as Vector<T> can serve for any type T.

Programming

Testing a Belief About Templates

Many learners meet templates for the first time with a particular picture in mind. They imagine that a templated function or class is a single piece of machinery that serves every element type, and that the program chooses among types while it runs. Under that picture, a generic vector would pay a price every time it touched an element, because the decision about what type it is handling would be made again and again during execution.

What do you think happens?

When a generic vector is used with several element types, when is the choice of element type made?

While the program runs, on every access to an element
Before the program runs, when the compiler processes the code

Reveal answer

Answer:

Before the program runs, when the compiler processes the code

Templates are a compile-time mechanism. When the program uses the template with a specific type argument, the compiler generates the code for that version before the program runs, so no type decision remains to be made at run time.

This article tests that belief. You will see how a single definition can serve many element types, how the compiler turns that definition into concrete code, and why the resulting code costs no more at run time than a version written by hand for one type.

Replacing a Type Name with a Stand-In

Suppose you already have a vector class that stores doubles. Every place in its code that mentions double could be replaced by a name that stands in for whatever type the user eventually needs. Once the element type is a stand-in, the class is no longer tied to one type, and the same definition can serve many element types. C++ calls this stand-in a template parameter, and the feature that makes it possible is called a template.

cpp

// Type-specific version: every element is a double
class DoubleVector {
public:
    explicit DoubleVector(int s);
    double& operator[](int i);
    int size() const;
private:
    double* elem;
    int sz;
};

// Type-specific version: every element is a double
class DoubleVector {
public:
    explicit DoubleVector(int s);
    double& operator[](int i);
    int size() const;
private:
    double* elem;
    int sz;
};

In the version below, the name T takes the place of double everywhere the element type appears. The name T is not yet a specific type. It is a parameter that will be filled in later by whoever uses the class.

cpp

template<typename T>
class Vector {
public:
    explicit Vector(int s);
    T& operator[](int i);
    int size() const;
private:
    T* elem;
    int sz;
};

template<typename T>
class Vector {
public:
    explicit Vector(int s);
    T& operator[](int i);
    int size() const;
private:
    T* elem;
    int sz;
};

Reading the template Prefix

The parameter is introduced by a prefix written directly before the declaration it governs. The prefix template<typename T> announces that T is a parameter of the declaration that follows it. You can read the prefix as C++'s counterpart to the mathematical phrase 'for all T', or more precisely 'for all types T'. The statement is not a claim about one type. It describes a family of declarations, one for each type you later choose.

Which part of the declaration introduces the parameter, which part names it, and which later uses of T refer back to it?

The member functions follow the same pattern. Each one is written with T in place of the old element type, and the template prefix must appear again in front of each out-of-class definition. In the source's example, the constructor checks for a negative size, allocates storage for T elements, and records the size, while the subscript operator checks that the index lies in range before returning a reference to the element.

cpp

template<typename T>
Vector<T>::Vector(int s)
{
    // check for a negative size, allocate T elements, record the size
}

template<typename T>
T& Vector<T>::operator[](int i)
{
    // check that i is in range, then return a reference to the element
}

template<typename T>
Vector<T>::Vector(int s)
{
    // check for a negative size, allocate T elements, record the size
}

template<typename T>
T& Vector<T>::operator[](int i)
{
    // check that i is in range, then return a reference to the element
}

class and typename Are Interchangeable

The prefix can use either of two keywords to introduce a type parameter. Older code often uses the keyword class, while newer code often uses typename. Both state that the name that follows is a type stand-in that the compiler will fill in later. Neither keyword makes the template behave differently, so template<class T> and template<typename T> introduce the same kind of type parameter. The choice is mainly a matter of which spelling a codebase uses.

Tracing Instantiation at Compile Time

Once the template exists, you use it by supplying a type argument inside angle brackets. Each supplied argument produces a vector whose element type is that argument. Each declaration below names a different element type, and each is a separate use of the same template.

cpp

Vector<int> ints(10);
Vector<double> doubles(10);
Vector<std::string> names(10);

Vector<int> ints(10);
Vector<double> doubles(10);
Vector<std::string> names(10);

What does the compiler generate from one Vector<T> definition when the program uses Vector<int> and Vector<double>, and when does that happen?

Each type argument triggers a compile-time instantiation. The step that generates the code for a particular version is called template instantiation, and it happens before the program runs. The generated code is what runs, so no type decision remains to be made at run time. Two declarations that use different arguments are therefore different vector types, even though they came from one template.

Nested Template Arguments

The same substitution works for element types that are themselves templates. In Vector<list<int>>, the element type is a list of integers, so the outer template receives list<int> as its argument. That makes this the most interesting of the three uses shown earlier.

cpp

Vector<list<int>> rows(5);

Vector<list<int>> rows(5);

Worked example

Reading a nested template argument

What element type does the outer Vector receive in Vector<list<int>>?

1
Find the outer template
The outer template is Vector, so the argument supplied to it is everything inside its outermost angle brackets.
2
Read the argument
The argument is list<int>, which is itself a template specialization.
3
Substitute for T
Wherever Vector's body writes T, the compiler substitutes list<int>. The element type is therefore a list of integers.

Result

The outer Vector's element type is list<int>.

Type Parameters Versus Value Parameters

A type parameter is not the only kind a template can take. In addition to type arguments, a template can take value arguments. A value parameter stands for a value rather than a type, and the caller supplies that value when the template is used. The source's example is Buffer, which takes a char type argument and a value argument named N.

How does a type argument differ from a value argument in what it supplies to the template, and where does each one appear?

cpp

Buffer<char, 256> small;
Buffer<char, 4096> large;

Buffer<char, 256> small;
Buffer<char, 4096> large;

Value arguments are useful when you want a buffer of a chosen size without asking the free store for memory at run time. The source explains that Buffer lets you create arbitrarily sized buffers with no overhead from the use of free store. Because the size is part of the type instantiation, it has to be fixed when the code is compiled. The template's implementation can make the size available to users through a type alias named value_type and a constexpr function, both of which give read-only access to the template arguments.

cpp

int n = 10;
Buffer<char, n> bad;      // n is a run-time value, not a constant expression

constexpr int m = 10;
Buffer<char, m> good;    // m is known at compile time

int n = 10;
Buffer<char, n> bad;      // n is a run-time value, not a constant expression

constexpr int m = 10;
Buffer<char, m> good;    // m is known at compile time

Why Templates Add No Run-Time Overhead

The source makes a concrete comparison. The code generated for Vector<double> is identical to the code generated for the Vector version from the earlier chapter, which was written for doubles alone. Using the template therefore adds nothing at run time beyond what a hand-written double version would already cost.

The standard-library vector<double> is likely to be better implemented, because more effort went into it. That is a statement about library quality, not about templates. The template mechanism itself is what makes the generic definition free at run time, because the work of choosing a type was already completed by the compiler.

Best practice

When you suspect a generic container is misbehaving, first ask which specific instantiation is involved. Each type argument you supply produces its own version of the code, so a mismatch usually traces back to the particular declaration whose argument differs from what you assumed.

Mistakes Beginners Make with Templates

Common mistake
Assuming one templated class is a single piece of machinery that picks types while the program runs
What it looks like
Believing that Vector<int> and Vector<double> share one set of code that checks the element type on every access
Why it fails
Each type argument triggers its own compile-time instantiation, so the compiler has already produced separate code for each type before the program runs.
Do this instead
Treat each specific use, such as Vector<int>, as a separate concrete version generated from the same template.
Common mistake
Omitting the template prefix on an out-of-class member definition
What it looks like
```
Writing Vector<T>::Vector(int s) without a template<typename T> line in front of it
```
Why it fails
The template prefix must appear again in front of each out-of-class definition, because it announces the parameter that the definition uses.
Do this instead
Place template<typename T> directly before every out-of-class member definition.
Common mistake
Using a run-time variable as a value argument
What it looks like
```
int n = 10; then Buffer<char, n> used as a type
```
Why it fails
A value argument must be a constant expression, because the size is part of the type and must be fixed at compile time.
Do this instead
Use a compile-time constant, such as a constexpr value or a literal, for the value argument.
Common mistake
Thinking class in the prefix restricts the argument to class types
What it looks like
Believing template<class T> cannot be used with Vector<int>
Why it fails
class and typename introduce the same kind of type parameter, and the keyword does not restrict the argument to class types.
Do this instead
Read both keywords as introducing a type stand-in, and supply any type as the argument.
Common mistake
Writing >> to close nested template lists in older compilers without a space, as in list<int>>

Practicing Template Instantiation

EASY

Given this template and the three declarations below, how many distinct vector types exist, and which parts of the code does the compiler generate separate versions for? Declarations: Vector<int> a(3); Vector<int> b(7); Vector<double> c(3).

Hints

Two declarations use the same type argument, so think about whether they produce the same concrete type.
Each distinct type argument produces its own instantiation, and the size passed to a constructor is a run-time value, not a type argument.

Your attempt (not saved)

MEDIUM

A colleague writes template<class T> class Stack and then uses Stack<int> and Stack<double>. Explain whether the keyword class restricts the template to class types, and state what instantiation happens for each use.