A Tour of C++

Previous Chapter

5 Essential Operations

7 Concepts and Generic Programming

6

Templates

Your quote here.

– B. Stroustrup

6.1 Introduction

Someone who wants a vector is unlikely always to want a vector of doubles. A vector is a general concept, independent of the notion of a floating-point number. Consequently, the element type of a vector ought to be represented independently. A template is a class or a function that we parameterize with a set of types or values. We use templates to represent ideas that are best understood as something general from which we can generate specific types and functions by specifying arguments, such as the vector’s element type double.

6.2 Parameterized Types

We can generalize our vector-of-doubles type to a vector-of-anything type by making it a template and replacing the specific type double with a type parameter. For example:

Click here to view code image

template<typename T>
class Vector {
private:
     T* elem;  // elem points to an array of sz elements of type T
     int sz;
public:
     explicit Vector(int s);          // constructor: establish invariant, acquire resources
     ~Vector() { delete[] elem; }     // destructor: release resources

     // ... copy and move operations ...

     T& operator[](int i);                     // for non-cost Vectors
     const T& operator[](int i) const;         // for const Vectors (§4.2.1)
     int size() const { return sz; }
};

The template<typename T> prefix makes T a parameter of the declaration it prefixes. It is C++’s version of the mathematical “for all T” or more precisely “for all types T.” If you want the mathematical “for all T, such that P(T),” you need concepts (§6.2.1, §7.2). Using class to introduce a type parameter is equivalent to using typename, and in older code we often see template<class T> as the prefix.

The member functions might be defined similarly:

Click here to view code image

template<typename T>
Vector<T>::Vector(int s)
{
     if (s<0)
           throw Negative_size{};
     elem = new T[s];
     sz = s;
}

template<typename T>
const T& Vector<T>::operator[](int i) const
{
     if (i<0 || size()<=i)
           throw out_of_range{"Vector::operator[]"};
     return elem[i];
}

Given these definitions, we can define Vectors like this:

Click here to view code image

Vector<char> vc(200);          // vector of 200 characters
Vector<string> vs(17);         // vector of 17 strings
Vector<list<int>> vli(45);     // vector of 45 lists of integers

The >> in Vector<list<int>> terminates the nested template arguments; it is not a misplaced input operator.

We can use Vectors like this:

Click here to view code image

void write(const Vector<string>& vs)        // Vector of some strings
{
     for (int i = 0; i!=vs.size(); ++i)
           cout << vs[i] << '\n';
}

To support the range-for loop for our Vector, we must define suitable begin() and end() functions:

Click here to view code image

template<typename T>
T* begin(Vector<T>& x)
{
    return x.size() ? &x[0] : nullptr;     // pointer to first element or nullptr
}

template<typename T>
T* end(Vector<T>& x)
{
    return x.size() ? &x[0]+x.size() : nullptr;     // pointer to one-past-last element
}

Given those, we can write:

Click here to view code image

void f2(Vector<string>& vs)   // Vector of some strings
{
     for (auto& s : vs)
           cout << s << '\n';
}

Similarly, we can define lists, vectors, maps (that is, associative arrays), unordered maps (that is, hash tables), etc., as templates (Chapter 11).

Templates are a compile-time mechanism, so their use incurs no run-time overhead compared to hand-crafted code. In fact, the code generated for Vector<double> is identical to the code generated for the version of Vector from Chapter 4. Furthermore, the code generated for the standard-library vector<double> is likely to be better (because more effort has gone into its implementation).

A template plus a set of template arguments is called an instantiation or a specialization. Late in the compilation process, at instantiation time, code is generated for each instantiation used in a program (§7.5). The code generated is type checked so that the generated code is as type safe as handwritten code. Unfortunately, that type check often occurs late in the compilation process, at instantiation time.

6.2.1 Constrained Template Arguments (C++20)

Most often, a template will make sense only for template arguments that meet certain criteria. For example, a Vector typically offers a copy operation, and if it does, it must require that its elements must be copyable. That is, we must require that Vector’s template argument is not just a typename but an Element where “Element” specifies the requirements of a type that can be an element:

Click here to view code image

template<Element T>
class Vector {
private:
     T* elem;  // elem points to an array of sz elements of type T
     int sz;
     // ...
};

This template<Element T> prefix is C++’s version of mathematic’s “for all T such that Element(T)”; that is, Element is a predicate that checks whether T has all the properties that a Vector requires. Such a predicate is called a concept (§7.2). A template argument for which a concept is specified is called a constrained argument and a template for which an argument is constrained is called a constrained template.

It is a compile-time error to try to instantiate a template with a type that does not meet its requirements. For example:

Click here to view code image

Vector<int> v1;     // OK: we can copy an int
Vector<thread> v2;  // error: we can't copy a standard thread (§15.2)

Since C++ does not officially support concepts before C++20, older code uses unconstrained template arguments and leaves requirements to documentation.

6.2.2 Value Template Arguments

In addition to type arguments, a template can take value arguments. For example:

Click here to view code image

template<typename T, int N>
struct Buffer {
     using value_type = T;
     constexprint size() { return N; }
     T[N];
     // ...
};

The alias (value_type) and the constexpr function are provided to allow users (read-only) access to the template arguments.

Value arguments are useful in many contexts. For example, Buffer allows us to create arbitrarily sized buffers with no use of the free store (dynamic memory):

Click here to view code image

Buffer<char,1024> glob;  // global buffer of characters (statically allocated)

void fct()
{
     Buffer<int,10> buf; // local buffer of integers (on the stack)
     // ...
}

A template value argument must be a constant expression.

6.2.3 Template Argument Deduction

Consider using the standard-library template pair:

pair<int,double> p = {1,5.2};

Many have found the need to specify the template argument types tedious, so the standard library offers a function, make_pair(), that deduces the template arguments of the pair it returns from its function arguments:

Click here to view code image

auto p = make_pair(1,5.2);    // p is a pair<int,double>

This leads to the obvious question “Why can’t we just deduce template parameters from constructor arguments?” So, in C++17, we can. That is:

Click here to view code image

pair p = {1,5.2};    // p is a pair<int,double>

This is not just a problem with pair; make_ functions are very common. Consider a simple example:

Click here to view code image

template<typename T>
class Vector {
public:
     Vector(int);
     Vector(initializer_list<T>);     // initializer-list constructor
     // ...
};

Vector v1 {1,2,3};   // deduce v1's element type from the initializer element type
Vector v2 = v1;      // deduce v2's element type from v1's element type

auto p = new Vector{1,2,3};   // p points to a Vector<int>

Vector<int> v3(1);  // here we need to be explicit about the element type (no element type is mentioned)

Clearly, this simplifies notation and can eliminate annoyances caused by mistyping redundant template argument types. However, it is not a panacea. Deduction can cause surprises (both for make_ functions and constructors). Consider:

Click here to view code image

Vector<string> vs1 {"Hello", "World"};  // Vector<string>
Vector vs {"Hello", "World"};           // deduces to Vector<const char*> (Surprise?)
Vector vs2 {"Hello"s, "World"s};        // deduces to Vector<string>
Vector vs3 {"Hello"s, "World"};         // error: the initializer list is not homogenous

The type of a C-style string literal is const char* (§1.7.1). If that was not what was intended, use the s suffix to make it a proper string (§9.2). If elements of an initializer list have differing types, we cannot deduce a unique element type, so we get an error.

When a template argument cannot be deduced from the constructor arguments, we can help by providing a deduction guide. Consider:

Click here to view code image

template<typename T>
class Vector2 {
public:
     using value_type = T;
     // ...
     Vector2(initializer_list<T>);   // initializer-list constructor

     template<typename Iter>
          Vector2(Iter b, Iter e);   // [b:e) range constructor
     // ...
};

Vector2 v1 {1,2,3,4,5};              // element type is int
Vector2 v2(v1.begin(),v1.begin()+2);

Obviously, v2 should be a Vector2<int>, but without help, the compiler cannot deduce that. The code only states that there is a constructor from a pair of values of the same type. Without language support for concepts (§7.2), the compiler cannot assume anything about that type. To allow deduction, we can add a deduction guide after the declaration of Vector:

Click here to view code image

template<typename Iter>
     Vector2(Iter,Iter) −> Vector2<typename Iter::value_type>;

That is, if we see a Vector2 initialized by a pair of iterators, we should deduce Vector2::value_type to be the iterator’s value type.

The effects of deduction guides are often subtle, so it is best to design class templates so that deduction guides are not needed. However, the standard library is full of classes that don’t (yet) use concepts (§7.2) and have such ambiguities, so it uses quite a few deduction guides.

6.3 Parameterized Operations

Templates have many more uses than simply parameterizing a container with an element type. In particular, they are extensively used for parameterization of both types and algorithms in the standard library (§11.6, §12.6).

There are three ways of expressing an operation parameterized by types or values:

A function template
A function object: an object that can carry data and be called like a function
A lambda expression: a shorthand notation for a function object

6.3.1 Function Templates

We can write a function that calculates the sum of the element values of any sequence that a range-for can traverse (e.g., a container) like this:

Click here to view code image

template<typename Sequence, typename Value>
Value sum(const Sequence& s, Value v)
{
     for (auto x : s)
           v+=x;
     return v;
}

The Value template argument and the function argument v are there to allow the caller to specify the type and initial value of the accumulator (the variable in which to accumulate the sum):

Click here to view code image

void user(Vector<int>& vi, list<double>& ld, vector<complex<double>>& vc)
{
     int x = sum(vi,0);                     // the sum of a vector of ints (add ints)
     double d = sum(vi,0.0);                // the sum of a vector of ints (add doubles)
     double dd = sum(ld,0.0);               // the sum of a list of doubles
     auto z = sum(vc,complex{0.0,0.0});     // the sum of a vector of complex<double>s
}

The point of adding ints in a double would be to gracefully handle a number larger than the largest int. Note how the types of the template arguments for sum<Sequence,Value> are deduced from the function arguments. Fortunately, we do not need to explicitly specify those types.

This sum() is a simplified version of the standard-library accumulate() (§14.3).

A function template can be a member function, but not a virtual member. The compiler would not know all instantiations of such a template in a program, so it could not generate a vtbl (§4.4).

6.3.2 Function Objects

One particularly useful kind of template is the function object (sometimes called a functor), which is used to define objects that can be called like functions. For example:

Click here to view code image

template<typename T>
class Less_than {
     const T val;   // value to compare against
public:
     Less_than(const T& v) :val{v} { }
     bool operator()(const T& x) const { return x<val; } // call operator
};

The function called operator() implements the “function call,” “call,” or “application” operator ().

We can define named variables of type Less_than for some argument type:

Click here to view code image

Less_than lti {42};                // lti(i) will compare i to 42 using < (i<42)
Less_than lts {"Backus"s};         // lts(s) will compare s to "Backus" using < (s<"Backus")
Less_than<string> lts2 {"Naur"};   // "Naur" is a C-style string, so we need <string> to get the right <

We can call such an object, just as we call a function:

Click here to view code image

void fct(int n, const string & s)
{
     bool b1 = lti(n);    // true if n<42
     bool b2 = lts(s);    // true if s<"Backus"
     // ...
}

Such function objects are widely used as arguments to algorithms. For example, we can count the occurrences of values for which a predicate returns true:

Click here to view code image

template<typename C, typename P>
     // requires Sequence<C> && Callable<P,Value_type<P>>
int count(const C& c, P pred)
{
     int cnt = 0;
     for (const auto& x : c)
           if (pred(x))
                 ++cnt;
     return cnt;
}

A predicate is something that we can invoke to return true or false. For example:

Click here to view code image

void f(const Vector<int>& vec, const list<string>& lst, int x, const string& s)
{
     cout << "number of values less than " << x << ": " << count(vec,Less_than{x}) << '\n';
     cout << "number of values less than " << s << ": " << count(lst,Less_than{s}) << '\n';
}

Here, Less_than{x} constructs an object of type Less_than<int>, for which the call operator compares to the int called x; Less_than{s} constructs an object that compares to the string called s. The beauty of these function objects is that they carry the value to be compared against with them. We don’t have to write a separate function for each value (and each type), and we don’t have to introduce nasty global variables to hold values. Also, for a simple function object like Less_than, inlining is simple, so a call of Less_than is far more efficient than an indirect function call. The ability to carry data plus their efficiency makes function objects particularly useful as arguments to algorithms.

Function objects used to specify the meaning of key operations of a general algorithm (such as Less_than for count()) are often referred to as policy objects.

6.3.3 Lambda Expressions

In §6.3.2, we defined Less_than separately from its use. That can be inconvenient. Consequently, there is a notation for implicitly generating function objects:

Click here to view code image

void f(const Vector<int>& vec, const list<string>& lst, int x, const string& s)
{
     cout << "number of values less than " << x
          << ": " << count(vec,[&](int a){ return a<x; })
          << '\n';
     cout << "number of values less than " << s
          << ": " << count(lst,[&](const string& a){ return a<s; })
          << '\n';
}

The notation [&](int a){ return a<x; } is called a lambda expression. It generates a function object exactly like Less_than<int>{x}. The [&] is a capture list specifying that all local names used in the lambda body (such as x) will be accessed through references. Had we wanted to “capture” only x, we could have said so: [&x]. Had we wanted to give the generated object a copy of x, we could have said so: [=x]. Capture nothing is [ ], capture all local names used by reference is [&], and capture all local names used by value is [=].

Using lambdas can be convenient and terse, but also obscure. For nontrivial actions (say, more than a simple expression), I prefer to name the operation so as to more clearly state its purpose and to make it available for use in several places in a program.

In §4.5.3, we noted the annoyance of having to write many functions to perform operations on elements of vectors of pointers and unique_ptrs, such as draw_all() and rotate_all(). Function objects (in particular, lambdas) can help by allowing us to separate the traversal of the container from the specification of what is to be done with each element.

First, we need a function that applies an operation to each object pointed to by the elements of a container of pointers:

Click here to view code image

template<typename C, typename Oper>
void for_all(C& c, Oper op)       // assume that C is a container of pointers
     // requires Sequence<C> && Callable<Oper,Value_type<C>> (see §7.2.1)
{
     for (auto& x : c)
           op(x);       // pass op() a reference to each element pointed to
}

Now, we can write a version of user() from §4.5 without writing a set of _all functions:

Click here to view code image

void user2()
{
     vector<unique_ptr<Shape>> v;
     while (cin)
          v.push_back(read_shape(cin));
     for_all(v,[](unique_ptr<Shape>& ps){ ps−>draw(); });        // draw_all()
     for_all(v,[](unique_ptr<Shape>& ps){ ps−>rotate(45); });    // rotate_all(45)
}

I pass a unique_ptr<Shape>& to a lambda so that for_all() doesn’t have to care exactly how the objects are stored. In particular, those for_all() calls do not affect the lifetime of the Shapes passed and the bodies of the lambdas use the argument just as if they had been a plain-old pointers.

Like a function, a lambda can be generic. For example:

Click here to view code image

template<class S>
void rotate_and_draw(vector<S>& v, int r)
{
     for_all(v,[](auto& s){ s−>rotate(r); s−>draw(); });
}

Here, like in variable declarations, auto means that any type is accepted as an initializer (an argument is considered to initialize the formal parameter in a call). This makes a lambda with an auto parameter a template, a generic lambda. For reasons lost in standards committee politics, this use of auto is not currently allowed for function arguments.

We can call this generic rotate_and_draw() with any container of objects that you can draw() and rotate(). For example:

Click here to view code image

void user4()
{
     vector<unique_ptr<Shape>> v1;
     vector<Shape*> v2;
     // ...
     rotate_and_draw(v1,45);
     rotate_and_draw(v2,90);
}

Using a lambda, we can turn any statement into an expression. This is mostly used to provide an operation to compute a value as an argument value, but the ability is general. Consider a complicated initialization:

Click here to view code image

enum class Init_mode { zero, seq, cpy, patrn };     // initializer alternatives

// messy code:

// int n, Init_mode m, vector<int>& arg, and iterators p and q are defined somewhere

vector<int> v;

switch (m) {
case zero:
     v = vector<int>(n);  // n elements initialized to 0
     break;
case cpy:
     v = arg;
     break;
};

// ...

if (m == seq)
      v.assign(p,q);      // copy from sequence [p:q)
// ...

This is a stylized example, but unfortunately not atypical. We need to select among a set of alternatives for initializing a data structure (here v) and we need to do different computations for different alternatives. Such code is often messy, deemed essential “for efficiency,” and a source of bugs:

The variable could be used before it gets its intended value.
The “initialization code” could be mixed with other code, making it hard to comprehend.
When “initialization code” is mixed with other code it is easier to forget a case.
This isn’t initialization, it’s assignment.

Instead, we could convert it to a lambda used as an initializer:

Click here to view code image

// int n, Init_mode m, vector<int>& arg, and iterators p and q are defined somewhere

vector<int> v = [&] {
     switch (m) {
     case zero:
          return vector<int>(n);       // n elements initialized to 0
     case seq:
          return vector<int>{p,q};     // copy from sequence [p:q)
     case cpy:
          return arg;
     }
}();
// ...

I still “forgot” a case, but now that’s easily spotted.

6.4 Template Mechanisms

To define good templates, we need some supporting language facilities:

Values dependent on a type: variable templates (§6.4.1).
Aliases for types and templates: alias templates (§6.4.2).
A compile-time selection mechanism: if constexpr (§6.4.3).
A compile-time mechanism to inquire about properties of types and expressions: requires-expressions (§7.2.3).

In addition, constexpr functions (§1.6) and static_asserts (§3.5.5) often take part in template design and use.

These basic mechanisms are primarily tools for building general, foundational abstractions.

6.4.1 Variable Templates

When we use a type, we often want constants and values of that type. This is of course also the case when we use a class template: when we define a C<T>, we often want constants and variables of type T and other types depending on T. Here is an example from a fluid dynamic simulation [Garcia,2015]:

Click here to view code image

template <class T>
     constexpr T viscosity = 0.4;

template <class T>
     constexpr space_vector<T> external_acceleration = { T{}, T{−9.8}, T{} };

auto vis2 = 2*viscosity<double>;
auto acc = external_acceleration<float>;

Here, space_vector is a three-dimensional vector.

Naturally, we can use arbitrary expressions of suitable type as initializers. Consider:

Click here to view code image

template<typename T, typename T2>
     constexpr bool Assignable = is_assignable<T&,T2>::value;  // is_assignable is a type trait (§13.9.1)

template<typename T>
void testing()
{
     static_assert(Assignable<T&,double>, "can't assign a double");
     static_assert(Assignable<T&,string>, "can't assign a string");
}

After some significant mutations, this idea becomes the heart of concept definitions (§7.2).

6.4.2 Aliases

Surprisingly often, it is useful to introduce a synonym for a type or a template. For example, the standard header <cstddef> contains a definition of the alias size_t, maybe:

using size_t = unsigned int;

The actual type named size_t is implementation-dependent, so in another implementation size_t may be an unsigned long. Having the alias size_t allows the programmer to write portable code.

It is very common for a parameterized type to provide an alias for types related to their template arguments. For example:

Click here to view code image

template<typename T>
class Vector {
public:
     using value_type = T;
     // ...
};

In fact, every standard-library container provides value_type as the name of its value type (Chapter 11). This allows us to write code that will work for every container that follows this convention. For example:

Click here to view code image

template<typename C>
using Value_type = typename C::value_type;     // the type of C's elements

template<typename Container>
void algo(Container& c)
{
     Vector<Value_type<Container>> vec;        // keep results here
     // ...
}

The aliasing mechanism can be used to define a new template by binding some or all template arguments. For example:

Click here to view code image

template<typename Key, typename Value>
class Map {
     // ...
};

template<typename Value>
using String_map = Map<string,Value>;

String_map<int> m;     // m is a Map<string,int>

6.4.3 Compile-Time `if`

Consider writing an operation that can use one of two operations slow_and_safe(T) or simple_and_fast(T). Such problems abound in foundational code where generality and optional performance are essential. The traditional solution is to write a pair of overloaded functions and select the most appropriate based on a trait (§13.9.1), such as the standard-library is_pod. If a class hierarchy is involved, a base class can provide the slow_and_safe general operation and a derived class can override with a simple_and_fast implementation.

In C++17, we can use a compile-time if:

Click here to view code image

template<typename T>
void update(T& target)
{
     // ...
     if constexpr(is_pod<T>::value)
          simple_and_fast(target); // for "plain old data"
     else
          slow_and_safe(target);
     // ...
}

The is_pod<T> is a type trait (§13.9.1) that tells us whether a type can be trivially copied.

Only the selected branch of an if constexpr is instantiated. This solution offers optimal performance and locality of the optimization.

Importantly, an if constexpr is not a text-manipulation mechanism and cannot be used to break the usual rules of grammar, type, and scope. For example:

Click here to view code image

template<typename T>
void bad(T arg)
{
     if constexpr(Something<T>::value)
          try{                         // syntax error

     g(arg);

     if constexpr(Something<T>::value)
          } catch(...) { /* ... */ }   // syntax error
}

Allowing such text manipulation could seriously compromise readability of code and create problems for tools relying on modern program representation techniques (such as “abstract syntax trees”).

6.5 Advice

[1] Use templates to express algorithms that apply to many argument types; §6.1; [CG: T.2].

[2] Use templates to express containers; §6.2; [CG: T.3].

[3] Use templates to raise the level of abstraction of code; §6.2; [CG: T.1].

[4] Templates are type safe, but checking happens too late; §6.2.

[5] Let constructors or function templates deduce class template argument types; §6.2.3.

[6] Use function objects as arguments to algorithms; §6.3.2; [CG: T.40].

[7] Use a lambda if you need a simple function object in one place only; §6.3.2.

[8] A virtual function member cannot be a template member function; §6.3.1.

[9] Use template aliases to simplify notation and hide implementation details; §6.4.2.

[10] To use a template, make sure its definition (not just its declaration) is in scope; §7.5.

[11] Templates offer compile-time “duck typing”; §7.5.

[12] There is no separate compilation of templates: #include template definitions in every translation unit that uses them.

Previous Chapter

5 Essential Operations

7 Concepts and Generic Programming