Skip to content

Chapter 7: Concepts and Generic Programming

7.1

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 and values.

7.2

templates may have constraints or requirements. We call these constrained templates *concepts.

7.2.1

Once we have defined what the concepts Sequence and Number mean, the compiler can reject bad calls by looking at sum() interface only.

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

The range_value_t of a sequence is the type of the elements in the sequence; it comes from the standard library where it names the type of the elements of a range. Arithmetic<X,Y> is a concept specifying that we can do artithmetic with numbers of types X and Y. This saves us from accidentally trying to calculate the sum() of a vector<string> or vector<int*> while still accepting vecotr<int> and vector<complex<double>>.

Unsurprisingly, requires Arithmetic<range_value_t<Seq>, Num> is called a requirements-clause. The template<Sequence Seq> notion is simply a shorthand for an explicit use of requires Sequence<Seq>, or we could also use the equivalence between the two notations.

// Explicitly write out all requirement clauses
template<typename Seq, typename Num>
    requires Sequence<Seq> && Number<Num> && Arithmetic<range_value_t<Seq>, Num>  // multiple requirement, all explicitly stated
Num sum(Seq s, Num n);

// Use Concepts directly with now requirement clauses
template<Sequence Seq, Arithmetic<range_value_t<Seq>> Num>
Num sum(Seq s, Num n);

// Before concepts are available to the compiler
template<typename Seq, typename Num>
// requires Arithmetic<range_value_t<Sequence>, Number>   // comment the requirement
Num sum(Seq s, Num n);

7.2.2

Like other overloading, choosing the concept overloading is a compile-time mechanism implying no run-tim costs, and where the compiler does not find a best choice, it gives an ambiguity error. The rules for cencept-based over-loading are far simpler than the rules for general overloading.

  • 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:

  • 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 arguments

7.2.3

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

using requires-expression, we can check if a set of expression is valid.

template<Forward_iterator Iter>
void advance(Iter p, int n){
    while (n--) ++p;
}

template<Forward_iterator Iter, int n>
    requires requires(Iter p, int i ) { p[i]; p+i; }  // this is not really correct, you should probably do p+=i;
void advance(Iter p, int n){
    p += n;
}

Note that requires requires is not a typo. The first requires starts the requirements-clauss 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 statement in it are valid code and false if they are not. requires-expressions should not be seen in "ordinary code." If you see requires requires. it is probably too low level.

7.2.4

How to define a new concept? The Ranges Technical Specification already offers a set for constraining standard-library algorithms. We can start with a simple example

template<typename T>
concept Equality_comparable = 
    requires(T a, T b){
        { a == b } -> bool;
        { a != b } -> bool; 
    };

// usage
static_assert(Equality_comparable<int>); // OK

struct S { int a;}
static_assert(Equality_comparable<S>); // ERROR

Equality_comparable is the concept we use to ensure that we can compare values of a type equal and non-equal. 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. Here we provide other examples

// Equality Comparable for Two Types
template<typename T, typename T2 = T>
concept Equality_comparable =
    requires(T a, T2 b){
        { a == b } -> std::same_as<bool>;
        { a != b } -> std::same_as<bool>;
        { b == a } -> std::same_as<bool>;
        { b != a } -> std::same_as<bool>;
    };

static_assert(Equality_comparable<int>); // OK. this still works
static_assert(Equality_comparable<int, double>); // OK

template<typename C>
using Value_type = typename C::value_type;

template<typename C>
using Iterator_type = typename C::iterator;

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

    { begin(a) } -> std::same_as<Iterator_type<S>>;  // include <concept>
    { end(a) } -> std::same_as<Iterator_type<S>>;

    requires std::same_as<Value_type<S>, Value_type<Iterator_type<S>>>;
    requires std::input_iterator<Iterator_type<S>>;  // include <iterators>
};

7.3

7.3.1

Good, useful concepts are fundamental and are discovered more than they are designed. A concept is not just a syntactic notion, it is fundamentally about semantics. Do not define semanticallly meaningless concepts, such as Addable and Subtractable. Instead, rely on domain knowledge to define conepts that match fundamental concepts in an application domain.

7.3.2

Good abstractions are carefully grown from concrete examples. 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.

7.4

A template can be defined to accept an arbitrary number of arguments of arbitrary types. Such a template is called a variadic template.

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

// a traditional way of handling variadic template
void print(){
    // what we do for no arguments: nothing
}
template<typename T, typename... Tail>
void print(T head, Tail... tail){
    cout << head << ' ';
    print(tail...);
}

// a way to avoid empty parameter
template<typename T, typename... Tail>
void print(T head, Tail... tail){
    cout << head << ' ';
    if constexpr(sizeof...(tail) > 0)  // here, `if constexpr` is the key to avoid print() with no parameter
        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.

WARNING variadic templates weakness

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

7.4.1

folding expression starting from C++17

template<Number... T>
int sum(T... v){
    return (v + ... + 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): (v0 + (v1 + (v2 + ... (vn + 0)))). That is, starting from the right where the 0 is. It is called a right fold. Alternatively, we can use a left fold

return (0 + ... + v);

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. 

template<typename... T>
void print(T&&... args){
    (std::cout << ... << args) << '\n';  // not that the entire fold expression need () 
    // this would be wrong, if we don't use () to isolate the fold expression for the rest.
    // std::cout << ... << args << '\n'; 
}

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

7.4.2

Passing arguments unchanged through an interface is an important use of variadic templates. 

template<typename Ttransport>  // an example from network transport level data class
    requires concepts::InputTransport<Transport>
class InputChannel {
public:
    // ...
    InputChannel(TransportArgs&&... transportArgs) : _transport(std::forward<TransportArgs>(transportArgs)...) {}
    // ...
    Transport _transport;
};
The standard-library function forward() 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.

7.5

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. Or -- using more technical terminology --we operate on values, and the presence and meaning of an opeartion depends solely on its operand values. This differes from the alternative view that objects have types, which determines the presence and meaning of operations. Value "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 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. In practice, this means that template definitions are typically found in header files, rather than .cpp files.

TODO

  • many example of concepts in this chapter was not the final format in C++ standard. Still needs to read the standard to learn more.