Templates in the Standard Library

Templates are a compile-time mechanism. The cost of generality is paid during compilation, when each concrete version is produced, and not during execution, when the generated code runs.

Programming

Testing a Belief About Generic Code

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 program that uses Vector<int> and Vector<double> runs, does it decide at run time which element type to handle?

Yes, the choice of element type is made on every element access while the program runs
No, the element types are handled before the program runs

Reveal answer

Answer:

No, the element types are handled before the program runs.

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

The rest of this article follows that belief as a question to test. You will see how one definition becomes many types, what the template prefix says, how the compiler produces concrete versions, why value arguments must be fixed at compile time, and why the result carries no extra run-time cost compared with a hand-written version.

One Definition, Many Element Types

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.

Definition

A template parameter is a stand-in name, such as T, that appears in a declaration in place of a concrete type. A template is the declaration that contains such parameters. Supplying a type argument for the parameter produces a specific version of the declaration, such as a vector whose element type is int.

How does a single Vector<T> definition relate to the many concrete vector types it can produce?

The diagram shows one definition at the top and several separate uses below it. Each use names a different element type, so each one is a different vector type, even though all of them came from the same template. The definition itself does not describe one type. It describes a family of declarations, one for each type you choose later.

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. Each piece of the prefix has a job, and the diagram below labels them in order.

Which part of the declaration introduces the parameter, and which part uses it?

The prefix does the introducing and the rest of the declaration does the using. The first T in the prefix creates the stand-in. Every later mention of T inside the class, such as the element type of its storage, refers back to that stand-in rather than to any particular type.

Using the Template with Type Arguments

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. The skeleton below is a simplified illustration of the shape of such a class. It is not a full implementation.

cpp

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

Vector<int> counts(10);
Vector<std::string> names(3);
Vector<double> prices(5);

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

Vector<int> counts(10);
Vector<std::string> names(3);
Vector<double> prices(5);

Worked example

Tracing Three Declarations of One Template

Starting from the template above, what does each of the three declarations produce, and how many different vector types appear?

1
Read the first declaration
Vector<int> counts(10) supplies int for T. The compiler produces a vector whose element type is int, and counts holds ten of them.
2
Read the second declaration
Vector<std::string> names(3) supplies std::string for T. This produces a different vector type, one whose elements are strings.
3
Read the third declaration
Vector<double> prices(5) supplies double for T. This is a third separate type, even though it came from the same template definition.
4
Count the distinct types
Each type argument produces its own version of the code. Three different arguments give three different vector types.

Result

The single template definition yields three distinct vector types, one for each type argument supplied.

The same substitution works when the element type is itself a template. In Vector<list<int>>, the element type is a list of integers, so the outer template receives list<int> as its argument. This is why that example is the most interesting of the three uses. The outer template does not care what its element type is built from; it only receives a type and stores elements of that type.

What the Compiler Produces

When the program uses Vector with a specific type argument, the compiler generates the code for that particular version. That generation step is called template instantiation, and it happens before the program runs. Each type argument you supply triggers its own instantiation. The pipeline below traces this for two uses of the same template.

What does the compiler produce when it sees Vector<int> and Vector<std::string>, and when does that happen?

The diagram shows that the template definition is not what the running program executes. The compiler reads each use, produces a concrete version for it, and only those concrete versions reach run time. Each version is a complete, ordinary piece of code with its element type already fixed.

Why Templates Add No Run-Time Cost

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. Because the generated code is the same, the template adds no run-time overhead beyond what a hand-written version would have. The source adds that the standard-library vector<double> is likely to be better implemented, because more effort went into it, but that is a statement about library quality rather than about templates.

Key point

Templates are a compile-time mechanism. The cost of generality is paid during compilation, when each concrete version is produced, and not during execution, when the generated code runs.

This is the answer to the belief from the start of the article. A generic vector does not decide its element type again on every access. It was already given a concrete type when the compiler instantiated it, so the element access at run time is the same kind of operation a hand-written type-specific vector would perform.

Value Parameters and Constant Expressions

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, written as Buffer<char,N>.

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. A value argument must therefore be a constant expression, meaning its value is known at compile time.

cpp

template<typename T, int N>
class Buffer {
public:
    // stores N elements of type T inside the object
};

Buffer<char, 256> line;   // 256 is a constant expression: allowed
const int size = 64;
Buffer<char, size> small; // size is a constant expression: allowed

template<typename T, int N>
class Buffer {
public:
    // stores N elements of type T inside the object
};

Buffer<char, 256> line;   // 256 is a constant expression: allowed
const int size = 64;
Buffer<char, size> small; // size is a constant expression: allowed

The implementation can make the size available to users through a type alias named value_type and a constexpr function. Both give read-only access to the template arguments, so user code can inspect the element type and size without changing them.

Feature	Type parameter	Value parameter
What it stands for	A type such as int or double	A value such as the size 256
How the caller supplies it	A type name inside angle brackets	A value inside angle brackets
Example from the source	The char in Buffer<char,N>	The N in Buffer<char,N>
Requirement on the argument	Must name a type	Must be a constant expression

Type parameters and value parameters differ in what they stand for and what the caller must supply.

Mistakes Beginners Make with Templates

Common mistake
Treating Vector<int> and Vector<double> as the same type
What it looks like
Vector<int> a; then Vector<double> b; and assuming a and b can be assigned to each other freely.
Why it fails
Each type argument produces its own version of the code. Two declarations with different arguments are different vector types, even though they came from one template.
Do this instead
Check which specific instantiation is involved. A mismatch usually traces back to the declaration whose argument differs from what you assumed.
Common mistake
Omitting the template prefix on an out-of-class member definition
What it looks like
Writing the body of Vector<T>::operator[] outside the class without repeating template<typename T> in front of it.
Why it fails
The template prefix must appear again in front of each out-of-class definition, because each one is a declaration governed by its own parameter.
Do this instead
Repeat the prefix template<typename T> directly before every out-of-class member definition.
Common mistake
Believing class and typename introduce different kinds of parameter
What it looks like
Thinking template<class T> only accepts class types while template<typename T> accepts any type.
Why it fails
The two keywords are interchangeable when they introduce a type parameter, and the keyword does not restrict the argument to class types.
Do this instead
Pick one spelling and follow the convention of the codebase. Both accept int, double, and other types.
Common mistake
Passing a run-time value as a value argument
What it looks like
Reading a size from input and writing Buffer<char, size> with that variable.
Why it fails
Value arguments must be constant expressions, because the size is part of the type and must be fixed when the code is compiled.
Do this instead
Use a literal or a constant whose value is known at compile time as the value argument.
Common mistake
Writing nested template arguments with >> and no space
What it looks like
Writing Vector<list<int>> in an older compiler setting where the two closing brackets were read as the input operator.
Why it fails
The sequence >> closes two template argument lists at once and does not behave as the input operator in that position. Earlier versions of C++ required a space between the two closing angle brackets.
Do this instead
Write a space between the two closing brackets if your compiler requires it. Later versions of C++ no longer need the space.

Practice: Counting Instantiations

EASY

Given these declarations using the same Vector template, how many distinct vector types are created? Vector<int> a(4); Vector<double> b(4); Vector<int> c(8); Vector<std::string> d(2);

Hints

Ask which type argument each declaration supplies, and ignore the size in parentheses for this question.
Two declarations that supply the same type argument produce the same vector type.
Count each distinct type argument once.

Your attempt (not saved)

MEDIUM

Explain, in two or three sentences, why a template that is instantiated for double adds no run-time cost compared with a hand-written vector of doubles.