A Tour of C++

7

Concepts and Generic Programming

Programming: you have to start with interesting algorithms.

– Alex Stepanov

7.1 Introduction

What are templates for? In other words, what programming techniques are effective when you use templates? Templates offer:

The ability to pass types (as well as values and templates) as arguments without loss of information. This implies excellent opportunities for inlining, of which current implementations take great advantage.
Opportunities to weave together information from different contexts at instantiation time. This implies optimization opportunities.
The ability to pass constant values as arguments. This implies the ability to do compile-time computation.

In other words, templates provide a powerful mechanism for compile-time computation and type manipulation that can lead to very compact and efficient code. Remember that types (classes) can contain both code (§6.3.2) and values (§6.2.2).

The first and most common use of templates is to support generic programming, that is, programming focused on the design, implementation, and use of general algorithms. Here, “general” means that an algorithm can be designed to accept a wide variety of types as long as they meet the algorithm’s requirements on its arguments. Together with concepts, the template is C++’s main support for generic programming. Templates provide (compile-time) parametric polymorphism.

7.2 Concepts (C++20)

Consider the sum() from §6.3.1:

Click here to view code image

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

It can be invoked for any data structure that supports begin() and end() so that the range-for will work. Such structures include the standard-library vector, list, and map. Furthermore, the element type of the data structure is limited only by its use: it must be a type that we can add to the Value argument. Examples are ints, doubles, and Matrixes (for any reasonable definition of Matrix). We could say that the sum() algorithm is generic in two dimensions: the type of the data structure used to store elements (“the sequence”) and the type of elements.

So, sum() requires that its first template argument is some kind of sequence and its second template argument is some kind of number. We call such requirements concepts.

Language support for concepts is not yet ISO C++, but it is an ISO Technical Specification [ConceptsTS]. Implementations are in use, so I risk recommending it here even though details are likely to change and it may be years before everybody can use it in production code.

7.2.1 Use of Concepts

Most template arguments must meet specific requirements for the template to compile properly and for the generated code to work properly. That is, most templates must be constrained templates (§6.2.1). The type-name introducer typename is the least constraining, requiring only that the argument be a type. Usually, we can do better than that. Consider that sum() again:

Click here to view code image

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

That’s much clearer. Once we have defined what the concepts Sequence and Number mean, the compiler can reject bad calls by looking at sum()’s interface only, rather than looking at its implementation. This improves error reporting.

However, the specification of sum()’s interface is not complete: I “forgot” to say that we should be able to add elements of a Sequence to a Number. We can do that:

Click here to view code image

template<Sequence Seq, Number Num>
    requires Arithmetic<Value_type<Seq>,Num>
Num sum(Seq s, Num n);

The Value_type of a sequence is the type of the elements in the sequence. Arithmetic<X,Y> is a concept specifying that we can do arithmetic with numbers of types X and Y. This saves us from accidentally trying to calculate the sum() of a vector<string> or a vector<int*> while still accepting vector<int> and vector<complex<double>>.

In this example, we needed only +=, but for simplicity and flexibility, we should not constrain our template argument too tightly. In particular, we might someday want to express sum() in terms of + and = rather than +=, and then we’d be happy that we used a general concept (here, Arithmetic) rather than a narrow requirement to “have +=.”

Partial specifications, as in the first sum() using concepts, can be very useful. Unless the specification is complete, some errors will not be found until instantiation time. However, partial specifications can help a lot, express intent, and are essential for smooth incremental development where we don’t initially recognize all the requirements we need. With mature libraries of concepts, initial specifications will be close to perfect.

Unsurprisingly, requires Arithmetic<Value_type<Seq>,Num> is called a requirements-clause. The template<Sequence Seq> notation is simply a shorthand for an explicit use of requires Sequence<Seq>. If I liked verbosity, I could equivalently have written

Click here to view code image

template<typename Seq, typename Num>
    requires Sequence<Seq> && Number<Num> && Arithmetic<Value_type<Seq>,Num>
Num sum(Seq s, Num n);

On the other hand, we could also use the equivalence between the two notations to write:

Click here to view code image

template<Sequence Seq, Arithmetic<Value_type<Seq>> Num>
Num sum(Seq s, Num n);

Where we cannot yet use concepts, we have to make do with naming conventions and comments, such as:

Click here to view code image

template<typename Sequence, typename Number>
    // requires Arithmetic<Value_type<Sequence>,Number>
Numer sum(Sequence s, Number n);

Whatever notation we chose, it is important to design a template with semantically meaningful constraints on its arguments (§7.2.4).

7.2.2 Concept-based Overloading

Once we have properly specified templates with their interfaces, we can overload based on their properties, much as we do for functions. Consider a slightly simplified standard-library function advance() that advances an iterator (§12.3):

Click here to view code image

template<Forward_iterator Iter>
void advance(Iter p, int n)        // move p n elements forward
{
     for (−−n)
           ++p;    // a forward iterator has ++, but not + or +=
}

template<Random_access_iterator Iter>
void advance(Iter p, int n)        // move p n elements forward
{
     p+=n;        // a random-access iterator has +=
}

The compiler will select the template with the strongest requirements met by the arguments. In this case, a list only supplies forward iterators, but a vector offers random-access iterators, so we get:

Click here to view code image

void user(vector<int>::iterator vip, list<string>::iterator lsp)
{
     advance(vip,10);   // use the fast advance()
     advance(lsp,10);   // use the slow advance()
}

Like other overloading, this is a compile-time mechanism implying no run-time cost, and where the compiler does not find a best choice, it gives an ambiguity error. The rules for concept-based overloading are far simpler than the rules for general overloading (§1.3). Consider first a single argument for several alternative functions:

If the argument doesn’t match the concept, that alternative cannot be chosen.
If the argument matches the concept for just one alternative, that alternative is chosen.
If arguments from two alternatives are equally good matches for a concept, we have an ambiguity.
If arguments from two alternatives match a concept and one is stricter than the other (match all the requirements of the other and more), that alternative is chosen.

For an alternative to be chosen it has to be

a match for all of its arguments, and
at least an equally good match for all arguments as other alternatives, and
a better match for at least one argument.

7.2.3 Valid Code

The question of whether a set of template arguments offers what a template requires of its template parameters ultimately boils down to whether some expressions are valid.

Using a requires-expression, we can check if a set of expressions is valid. For example:

Click here to view code image

template<Forward_iterator Iter>
void advance(Iter p, int n)        // move p n elements forward
{
     for (−−n)
           ++p;    // a forward iterator has ++, but not + or +=
}

template<Forward_iterator Iter, int n>
     requires requires(Iter p, int i) { p[i]; p+i; }     // Iter has subscripting and addition
void advance(Iter p, int n)            // move p n elements forward
{
     p+=n;           // a random-access iterator has +=
}

No, that requires requires is not a typo. The first requires starts the requirements-clause and the second requires starts the requires-expression

requires(Iter p, int i) { p[i]; p+i; }

A requires-expression is a predicate that is true if the statements in it are valid code and false if they are not.

I consider requires-expressions the assembly code of generic programming. Like ordinary assembly code, requires-expressions are extremely flexible and impose no programming discipline. In some form or other, they are at the bottom of most interesting generic code, just as assembly code is at the bottom of most interesting ordinary code. Like assembly code, requires-expressions should not be seen in “ordinary code.” If you see requires requires in your code, it is probably too low level.

The use of requires requires in advance() is deliberately inelegant and hackish. Note that I “forgot” to specify += and the required return types for the operations. You have been warned! Prefer named concepts for which the name indicates its semantic meaning.

Prefer use of properly named concepts with well-specified semantics (§7.2.4) and use requires-expressions in the definition of those.

7.2.4 Definition of Concepts

Eventually, we expect to find useful concepts, such as Sequence and Arithmetic in libraries, including the standard library. The Ranges Technical Specification [RangesTS] already offers a set for constraining standard-library algorithms (§12.7). However, simple concepts are not hard to define.

A concept is a compile-time predicate specifying how one or more types can be used. Consider first one of the simplest examples:

Click here to view code image

template<typename T>
concept Equality_comparable =
    requires (T a, T b) {
         { a == b } −> bool;   // compare Ts with ==
         { a != b } −> bool;   // compare Ts with !=
    };

Equality_comparable is the concept we use to ensure that we can compare values of a type equal and non-equal. We simply say that, given two values of the type, they must be comparable using == and != and the result of those operations must be convertible to bool. For example:

Click here to view code image

static_assert(Equality_comparable<int>);   // succeeds

struct S { int a; };
static_assert(Equality_comparable<S>);     // fails because structs don't automatically get == and !=

The definition of the concept Equality_comparable is exactly equivalent to the English description and no longer. The value of a concept is always bool.

Defining Equality_comparable to handle nonhomogeneous comparisons is almost as easy:

Click here to view code image

template<typename T, typename T2 =T>
concept Equality_comparable =
    requires (T a, T2 b) {
         { a == b } −> bool;  // compare a T to a T2 with ==
         { a != b } −> bool;  // compare a T to a T2 with !=
         { b == a } −> bool;  // compare a T2 to a T with ==
         { b != a } −> bool;  // compare a T2 to a T with !=
    };

The typename T2 =T says that if we don’t specify a second template argument, T2 will be the same as T; T is a default template argument.

We can test Equality_comparable like this:

Click here to view code image

static_assert(Equality_comparable<int,double>);  // succeeds
static_assert(Equality_comparable<int>);         // succeeds (T2 is defaulted to int)
static_assert(Equality_comparable<int,string>);  // fails

For a more complex example, consider a sequence:

Click here to view code image

template<typename S>
concept Sequence = requires(S a) {
     typename Value_type<S>;             // S must have a value type.
     typename Iterator_type<S>;          // S must have an iterator type.

     { begin(a) } −> Iterator_type<S>;   // begin(a) must return an iterator
     { end(a) } −> Iterator_type<S>;     // end(a) must return an iterator

     requires Same_type<Value_type<S>,Value_type<Iterator_type<S>>>;
     requires Input_iterator<Iterator_type<S>>;
};

For a type S to be a Sequence, it must provide a Value_type (the type of its elements) and an Iterator_type (the type of its iterators; see §12.1). It must also ensure that there exist begin() and end() functions that return iterators, as is idiomatic for standard-library containers (§11.3). Finally, the Iterator_type really must be an input_iterator with elements of the same type as the elements of S.

The hardest concepts to define are the ones that represent fundamental language concepts. Consequently, it is best to use a set from an established library. For a useful collection, see §12.7.

7.3 Generic Programming

The form of generic programming supported by C++ centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software [Stepanov,1989]. The abstractions representing the fundamental operations and data structures are called concepts; they appear as requirements for template parameters.

7.3.1 Use of Concepts

Good, useful concepts are fundamental and are discovered more than they are designed. Examples are integer and floating-point number (as defined even in Classic C), sequence, and more general mathematical concepts, such as field and vector space. They represent the fundamental concepts of a field of application. That is why they are called “concepts.” Identifying and formalizing concepts to the degree necessary for effective generic programming can be a challenge.

For basic use, consider the concept Regular (§12.7). A type is regular when it behaves much like an int or a vector. An object of a regular type

can be default constructed.
can be copied (with the usual semantics of copy, yielding two objects that are independent and compare equal) using a constructor or an assignment.
can be compared using == and !=.
doesn’t suffer technical problems from overly clever programming tricks.

A string is another example of a regular type. Like int, string is also StrictTotallyOrdered (§12.7). That is, two strings can be compared using <, <=, >, and >= with the appropriate semantics.

A concept is not just a syntactic notion, it is fundamentally about semantics. For example, don’t define + to divide; that would not match the requirements for any reasonable number. Unfortunately, we do not yet have any language support for expressing semantics, so we have to rely on expert knowledge and common sense to get semantically meaningful concepts. Do not define semantically meaningless concepts, such as Addable and Subtractable. Instead, rely on domain knowledge to define concepts that match fundamental concepts in an application domain.

7.3.2 Abstraction Using Templates

Good abstractions are carefully grown from concrete examples. It is not a good idea to try to “abstract” by trying to prepare for every conceivable need and technique; in that direction lies inelegance and code bloat. Instead, start with one – and preferably more – concrete examples from real use and try to eliminate inessential details. Consider:

Click here to view code image

double sum(const vector<int>& v)
{
    double res = 0;
    for (auto x : v)
         res += x;
    return res;
}

This is obviously one of many ways to compute the sum of a sequence of numbers.

Consider what makes this code less general than it needs to be:

Why just ints?
Why just vectors?
Why accumulate in a double?
Why start at 0?
Why add?

Answering the first four questions by making the concrete types into template arguments, we get the simplest form of the standard-library accumulate algorithm:

Click here to view code image

template<typename Iter, typename Val>
Val accumulate(Iter first, Iter last, Val res)
{
     for (auto p = first; p!=last; ++p)
           res += *p;
     return res;
}

Here, we have:

The data structure to be traversed has been abstracted into a pair of iterators representing a sequence (§12.1).
The type of the accumulator has been made into a parameter.
The initial value is now an input; the type of the accumulator is the type of this initial value.

A quick examination or – even better – measurement will show that the code generated for calls with a variety of data structures is identical to what you get from the hand-coded original example. For example:

Click here to view code image

void use(const vector<int>& vec, const list<double>& lst)
{
     auto sum = accumulate(begin(vec),end(vec),0.0); // accumulate in a double
     auto sum2 = accumulate(begin(lst),end(lst),sum);
     //
}

The process of generalizing from a concrete piece of code (and preferably from several) while preserving performance is called lifting. Conversely, the best way to develop a template is often to

first, write a concrete version
then, debug, test, and measure it
finally, replace the concrete types with template arguments.

Naturally, the repetition of begin() and end() is tedious, so we can simplify the user interface a bit:

Click here to view code image

template<Range R, Number Val>   // a Range is something with begin() and end()
Val accumulate(R r, Val res = 0)
{
     for (auto p = begin(r); p!=end(r); ++p)
           res += *p;
     return res;
}

For full generality, we can abstract the += operation also; see §14.3.

7.4 Variadic Templates

A template can be defined to accept an arbitrary number of arguments of arbitrary types. Such a template is called a variadic template. Consider a simple function to write out values of any type that has a << operator:

Click here to view code image

void user()
{
     print("first: ", 1, 2.2, "hello\n"s);              // first: 1 2.2 hello

     print("\nsecond: ", 0.2, 'c', "yuck!"s, 0, 1, 2, '\n');   // second: 0.2 c yuck! 0 1 2
}

Traditionally, implementing a variadic template has been to separate the first argument from the rest and then recursively call the variadic template for the tail of the arguments:

Click here to view code image

void print()
{
     // what we do for no arguments: nothing
}

template<typename T, typename ... Tail>
void print(T head, Tail... tail)
{
     // what we do for each argument, e.g.,
     cout << head << ' ';
     print(tail...);
}

The typename ... indicates that Tail is a sequence of types. The Tail... indicates that tail is a sequence of values of the types in Tail. A parameter declared with a ... is called a parameter pack. Here, tail is a (function argument) parameter pack where the elements are of the types found in the (template argument) parameter pack Tail. So, print() can take any number of arguments of any types.

A call of print() separates the arguments into a head (the first) and a tail (the rest). The head is printed and then print() is called for the tail. Eventually, of course, tail will become empty, so we need the no-argument version of print() to deal with that. If we don’t want to allow the zero-argument case, we can eliminate that print() using a compile-time if:

Click here to view code image

template<typename T, typename ... Tail>
void print(T head, Tail... tail)
{
     cout << head << ' ';
     if constexpr(sizeof...(tail)> 0)
          print(tail...);
}

I used a compile-time if (§6.4.3), rather than a plain run-time if to avoid a final, never called, call print() from being generated.

The strength of variadic templates (sometimes just called variadics) is that they can accept any arguments you care to give them. Weaknesses include

The recursive implementations can be tricky to get right.
The recursive implementations can be surprisingly expensive in compile time.
The type checking of the interface is a possibly elaborate template program.

Because of their flexibility, variadic templates are widely used in the standard library, and occasionally wildly overused.

7.4.1 Fold Expressions

To simplify the implementation of simple variadic templates, C++17 offers a limited form of iteration over elements of a parameter pack. For example:

Click here to view code image

template<Number... T>
int sum(T... v)
{
  return (v + ... + 0);     // add all elements of v starting with 0
}

Here, sum() can take any number of arguments of any types. Assuming that sum() really adds its arguments, we get:

Click here to view code image

int x = sum(1, 2, 3, 4, 5);  // x becomes 15
int y = sum('a', 2.4, x);    // y becomes 114 (2.4 is truncated and the value of 'a' is 97)

The body of sum uses a fold expression:

Click here to view code image

return (v + ... + 0);   // add all elements of v to 0

Here, (v+...+0) means add all the elements of v starting with the initial value 0. The first element to be added is the “rightmost” (the one with the highest index): (v[0]+(v[1]+(v[2]+(v[3]+(v[4]+0))))). That is, starting from the right where the 0 is. It is called a right fold. Alternatively, we could have used a left fold:

Click here to view code image

template<Number ... T>
int sum2(T... v)
{
  return (0 + ... + v); // add all elements of v to 0
}

Now, the first element to be added is the “leftmost” (the one with the lowest index): (((((0+v[0])+v[1])+v[2])+v[3])+v[4]). That is, starting from the left where the 0 is.

Fold is a very powerful abstraction, clearly related to the standard-library accumulate(), with a variety of names in different languages and communities. In C++, the fold expressions are currently restricted to simplify the implementation of variadic templates. A fold does not have to perform numeric computations. Consider a famous example:

Click here to view code image

template<typename ...T>
void print(T&&... args)
{
  (std::cout << ... << args) << '\n';  // print all arguments
}

print("Hello!"s,' ',"World ",2017);    // (((((std::cout << "Hello!"s) << ' ') << "World ") << 2017) << '\n');

Many use cases simply involve a set of values that can be converted to a common type. In such cases, simply copying the arguments into a vector or the desired type often simplifies further use:

Click here to view code image

template<typename Res, typename... Ts>
vector<Res> to_vector(Ts&&... ts)
{
     vector<Res> res;
     (res.push_back(ts) ...);   // no initial value needed
     return res;
}

We can use to_vector like this:

Click here to view code image

auto x = to_vector<double>(1,2,4.5,'a');

template<typename ... Ts>
int fct(Ts&&... ts)
{
     auto args = to_vector<string>(ts...);    // args[i] is the ith argument
     // ... use args here ...
}

int y = fct("foo", "bar", s);

7.4.2 Forwarding Arguments

Passing arguments unchanged through an interface is an important use of variadic templates. Consider a notion of a network input channel for which the actual method of moving values is a parameter. Different transport mechanisms have different sets of constructor parameters:

Click here to view code image

template<typename Transport>
  requires concepts::InputTransport<Transport>
class InputChannel {
public:
     // ...
   InputChannel(TransportArgs&&... transportArgs)
     : _transport(std::forward<TransportArgs>(transportArgs)...)
   {}
   // ...
   Transport _transport;
};

The standard-library function forward() (§13.2.2) is used to move the arguments unchanged from the InputChannel constructor to the Transport constructor.

The point here is that the writer of InputChannel can construct an object of type Transport without having to know what arguments are required to construct a particular Transport. The implementer of InputChannel needs only to know the common user interface for all Transport objects.

Forwarding is very common in foundational libraries where generality and low run-time overhead are necessary and very general interfaces are common.

7.5 Template Compilation Model

Assuming concepts (§7.2), the arguments for a template are checked against its concepts. Errors found here will be reported and the programmer has to fix the problems. What cannot be checked at this point, such as arguments for unconstrained template arguments, is postponed until code is generated for the template and a set of template arguments: “at template instantiation time.” For pre-concept code, this is where all type checking happens. When using concepts, we get here only after concept checking succeeded.

An unfortunate side effect of instantiation-time (late) type checking is that a type error can be found uncomfortably late and can result in spectacularly bad error messages because the compiler found the problem only after combining information from several places in the program.

The instantiation-time type checking provided for templates checks the use of arguments in the template definition. This provides a compile-time variant of what is often called duck typing (“If it walks like a duck and it quacks like a duck, it’s a duck”). Or – using more technical terminology – we operate on values, and the presence and meaning of an operation depend solely on its operand values. This differs from the alternative view that objects have types, which determine the presence and meaning of operations. Values “live” in objects. This is the way objects (e.g., variables) work in C++, and only values that meet an object’s requirements can be put into it. What is done at compile time using templates mostly does not involve objects, only values. The exception is local variables in a constexpr function (§1.6) that are used as objects inside the compiler.

To use an unconstrained template, its definition (not just its declaration) must be in scope at its point of use. For example, the standard header <vector> holds the definition of vector. In practice, this means that template definitions are typically found in header files, rather than .cpp files. This changes when we start to use modules (§3.3). Using modules, the source code is organized in the same way for ordinary functions and template functions. In both cases, definitions will be protected against the problems of textual inclusion.

7.6 Advice

[1] Templates provide a general mechanism for compile-time programming; §7.1.

[2] When designing a template, carefully consider the concepts (requirements) assumed for its template arguments; §7.3.2.

[3] When designing a template, use a concrete version for initial implementation, debugging, and measurement; §7.3.2.

[4] Use concepts as a design tool; §7.2.1.

[5] Specify concepts for all template arguments; §7.2; [CG: T.10].

[6] Whenever possible use standard concepts (e.g., the Ranges concepts); §7.2.4; [CG: T.11].

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

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

[9] Use templates to express containers and ranges; §7.3.2; [CG: T.3].

[10] Avoid “concepts” without meaningful semantics; §7.2; [CG: T.20].

[11] Require a complete set of operations for a concept; §7.2; [CG: T.21].

[12] Use variadic templates when you need a function that takes a variable number of arguments of a variety of types; §7.4.

[13] Don’t use variadic templates for homogeneous argument lists (prefer initializer lists for that); §7.4.

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

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

Table of Contents for A Tour of C++

7

7.1 Introduction

7.2 Concepts (C++20)

7.2.1 Use of Concepts

7.2.2 Concept-based Overloading

7.2.3 Valid Code

7.2.4 Definition of Concepts

7.3 Generic Programming

7.3.1 Use of Concepts

7.3.2 Abstraction Using Templates

7.4 Variadic Templates

7.4.1 Fold Expressions

7.4.2 Forwarding Arguments

7.5 Template Compilation Model

7.6 Advice

Table of Contents for
A Tour of C++