Feedback form for Lecture 8

Please fill in the feedback form for lecture 8.

1 Introduction to metaprogramming

C++ metaprogramming allows you to generate code in the form of templates, and to modify or augment the behaviour of your program, at compile time, based on the types or values of arguments. Note that this is not the same as reflection — we’ll get that in C++20 C++23 C++26 (hopefully) — which usually refers to runtime manipulation.

In C++, metaprogramming entirely revolves around templates, but you should already be familiar with those (at least the basics) from the previous lectures.

2 Constexpr

One of the features you might have noticed being used without much explanation is constexpr. This essentially denotes compile-time stuff, but the meaning differs slightly depending on where it’s used.

Note that constexpr is distinct from const; while constexpr implies const, the converse is not true. constexpr must have values known at compile-time, while const variables can be initialised with runtime values — just that they can’t be changed.

2.1 Constant expressions

Before we talk about constexpr itself, we need to discuss what core constant expressions are. Essentially, they are expressions that can be evaluated at compile-time. They can be used as array sizes, non-type template arguments, etc. Note that core constant expressions are not limited to constexpr settings. For example, the following is valid:

const int N = 16;
std::array<int, N> xs{};

Here, N was not constexpr, but it was usable in a constant expression, because it fulfilled these criteria:

• is a constexpr variable, OR
• is a constant-initialised variable of reference type or integral/enumeration type
  • note that “constant-initialised” means initialised with a constant expression (slightly recursive here)

2.1.1 Restrictions of constant expressions

Strangely enough, core constant expressions are defined negatively, that is in terms of a blacklist of the types of things that can be evaluated in it. If none of those things are evaluated, then the expression qualifies as a core constant expression.

We won’t give the entire list (it’s too long), but some of the more important ones are:

• a call to a non-constexpr function (including constructors)
• any expression whose evaluation would produce undefined behaviour (eg. division by 0)
• reinterpret_cast, including any conversion from void* to pointer-to-object
• a throw expression
• …

The key thing is that it only counts if the disqualifying expression is evaluated — you can put these things in a constexpr function as long as control flow would not cause them to be evaluated. Even so, there are a few more restrictions on constexpr functions themselves which we’ll discuss below.

2.2 constexpr variables

The first use of constexpr is on variables; this means that their value is available at compile time, and can be used in constant expressions. It’s just another specifier, and appears in much of the same places as one might see const:

constexpr int x = 0;

struct Foo {
  static constexpr int x = 10;
};

Note that constexpr data members (in structs) must be static.

2.3 constexpr functions

The next use of constexpr is to mark functions, and it means that you can use that function to compute values at compile-time to get a constant expression. For example:

constexpr int square(int x) {  //
  return x * x;
}

As we mentioned above, as long as an expression is not evaluated, there’s isn’t a problem with it being non-constexpr. This means that the following function still qualifies as constexpr:

constexpr int rectangle(int x, int y) {
  if (x < 0 || y < 0) {
    puts("your rectangle is wrong");
    return 0;
  } else {
    return x * y;
  }
}

We can call this function at compile-time (and use it in situations where we need a constant expression), as long as we don’t evaluate the puts call (which is obviously not constexpr):

constexpr int rekt = rectangle(69, 420);
static_assert(rekt == 28980);

On the other hand, if we tried to call the function and control flow would result in a call to a non-constexpr function, then the result of the call is no longer a constant expression:

constexpr int rekt = rectangle(-1, -2);

$ make broken1.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken1.o broken1.cpp
broken1.cpp:18:19: error: constexpr variable 'rekt' must be initialized by a constant expression
    constexpr int rekt = rectangle(-1, -2);
                  ^      ~~~~~~~~~~~~~~~~~
broken1.cpp:8:5: note: non-constexpr function 'puts' cannot be used in a constant expression
    puts("your rectangle is wrong");
    ^
broken1.cpp:18:26: note: in call to 'rectangle(-1, -2)'
    constexpr int rekt = rectangle(-1, -2);
                         ^
/usr/include/stdio.h:632:12: note: declared here
extern int puts (const char *__s);
           ^
1 error generated.
make: *** [Makefile:25: broken1.o] Error 1

As we’ll see later though, constexpr just means that the function can be used to produce a constant expression — not that it must produce one.

Finally, note that functions declared constexpr or consteval are implicitly also inline.

2.3.1 consteval functions

C++20 introduces the consteval specifier, which means that the evaluation of a function must happen at compile time. This means that it cannot be called with any runtime values.

For instance, if we made square consteval instead, then even at -O0, we don’t need any tricks to make the compiler evaluate the function at compile-time:

consteval int square2(int x) {  //
  return x * x;
}

Note that consteval is stronger than constexpr, so we don’t (and can’t) make a function both constexpr and consteval.

If we try to call the function with a (potentially) runtime value:

int k = 69;
int x = square2(k);

$ make broken2.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken2.o broken2.cpp
broken2.cpp:18:13: error: call to consteval function 'square2' is not a constant expression
    int x = square2(k);
            ^
broken2.cpp:18:21: note: read of non-const variable 'k' is not allowed in a constant expression
    int x = square2(k);
                    ^
broken2.cpp:17:9: note: declared here
    int k = 69;
        ^
1 error generated.
make: *** [Makefile:25: broken2.o] Error 1

There are other restrictions on consteval functions that go beyond constexpr, like not being able to take pointers to them (unless you are also in a consteval context). Those rules are meant to prevent consteval functions from “escaping” to runtime.

2.3.2 Formal requirements of constexpr functions

More formally, constexpr functions must satisfy the following requirements:

1. Its return type and parameters (if any) must be literal types (ie. satisfy the LiteralType requirement)
2. For constructors and destructors, the class must not have any virtual base classes
3. It must not contain any of the following (or be = default or = delete):
   • goto statements
   • labels other than those inside switch-case statements
   • definitions of variables with non-literal types
   • definitions of variables with static or thread-local storage duration
4. There is at least one set of arguments such that the function evaluates to a constant expression

2.3.3 constexpr lambdas

You can also mark lambdas as constexpr or consteval (covered below), like so:

[](auto a) constexpr {
  /* ... */
};

This appears in the same place as mutable. This isn’t usually required though, because lambdas are specified to be implicitly constexpr if it satisfies all the requirements. The effect of this is to mark the overloaded operator() as constexpr or consteval respectively.

2.3.4 Uses of constexpr functions

One interesting use-case for constexpr functions is to perform arbitrary computation at compile-time. For example, you can construct lookup tables in code instead of writing them out by hand.

For example, let’s say we wanted to have a table of all the powers of 10 - 1 (so 9, 99, 999, etc.). We could have code like this:

constexpr std::array<int, 8> xs = {
  9, 99, 999, 9999, 99999, 999999, 9999999, 99999999
};

or, we could be fancy and do something like this instead:

constexpr std::array<int, 8> xs = []() {
  std::array<int, 8> ret{};
  int foo = 10;
  for (size_t i = 0; i < 8; i++) {
    ret[i] = foo - 1;
    foo *= 10;
  }
  return ret;
}();

Here, we used an immediately-invoked lambda expression to return the result, since we need to initialise the the variable immediately with some non-trivial code. This is fine because lambdas are implicitly constexpr when possible, and std::array is a literal type.

Of course this is a little contrived, but you can imagine scenarios with more complicated lookup tables. For an interesting talk about how far you can take constexpr, you can watch this talk by Jason Turner.

Note that constant-initialised variables will end up in the .data or .rodata section in the final executable, so they’re pretty much the same as you just writing out the data yourself.

2.4 LiteralType named requirement

As we saw above, constexpr functions and variables need to have a “literal type”, which is actually a named requirement, like the iterator categories (ForwardIterator, BidirectionalIterator, etc.) we saw before.

A LiteralType is any of the following:

• a void type
• a scalar type (booleans, integers, floating-point, pointers, enumerations)
• a reference type
• a class type with the following properties:
  • has a constexpr destructor
  • is either an aggregate, or has at least one non-move non-copy constexpr constructor, or is a compiler-generated lambda type
  • all data members and base classes also satisfy LiteralType, and are not volatile
  • (for unions only) at least one data member satisfies LiteralType and is not volatile

Note that for class types, its constexpr constructors don’t actually need to be accessible (in terms of public/private) or even available (it can be delete-ed) for it to qualify as a literal type.

2.5 Enforcing compile-time evaluation

One of the things that we need to take note of is that the compiler is not actually required to evaluate the function call at compile time! It is perfectly valid for it to actually just call the function at runtime.

For example, if we compile the following code and look at its assembly:

printf("5*5 = %d\n",  //
       square(5));    //

$ ./main.out | sed '1,/<1/d;/1>/,$d'
5*5 = 25

main:       # @main
    push    rbp
    mov     rbp, rsp
    mov     edi, 5
    call    square(int) # here
    mov     esi, eax
    movabs  rdi, offset .L.str
    mov     al, 0
    call    printf
    xor     eax, eax
    pop     rbp
    ret

Here, we can see that the compiler still generated a call to the square function, even though it could have evaluated it at runtime and replaced it with the constant 25. Note this is with no optimisations (-O0); if we used -O1 or above, then we get the expected behaviour — but that would also be the case if the function was not constexpr!

Of course, note that the compiler still needs to actually emit code for the function, and it might need to call it at runtime in legitimate cases — when the arguments are not known at compile time.

Either way, we can sort of get around this and force compile-time evaluation by assigning to a constexpr variable first:

constexpr int x = square(5);
printf("5*5 = %d\n", x);

main:       # @main
    push    rbp
    mov     rbp, rsp
    sub     rsp, 16
    mov     dword ptr [rbp - 4], 25
    movabs  rdi, offset .L.str
    mov     esi, 25     # here
    mov     al, 0
    call    printf
    xor     eax, eax
    add     rsp, 16
    pop     rbp
    ret

Note that this is done with no optimisations. However, this behaviour isn’t actually guaranteed by the standard; it just so happens that most compilers will compute assignments to constexpr.

template <auto X>
constexpr auto force_compile_time() {
  return X;
}

constexpr int x = force_compile_time<square(4)>();

We also have the consteval specifier for functions as mentioned above, which enforces that all calls to that function must produce a constant expression.

2.6 constinit specifier

One last specifier that we have is constinit, which is applied to variables. When a variable is specified as such, it is an assertion that the variable must be initialised with a constant expression. However, unlike constexpr, it does not require that the variable be const-qualified.

That is, the following is valid:

static constinit int x  //
    = square(10);
x = 50;

std::cout << "x = "  //
          << x << "\n";

$ ./main.out | sed '1,/<2/d;/2>/,$d'
x = 50

Note that local variables cannot be declared constinit — only variables with static or thread-local storage duration.

One of the main motivators for constinit is to avoid runtime initialisation of static variables, due to static initialisation order fiasco. This way, we can be sure that the initialisation is run at compile-time with a constant expression.

2.7 Constexpr-if

Lastly on the constexpr list, we have if-constexpr. This essentially allows us to check conditions at compile-time, and we already saw some of this previously:

template <typename T>
constexpr bool is_arr() {
  if constexpr (std::is_array_v<T>) {
    return true;
  } else {
    return false;
  }
}

std::cout << (is_arr<int[]>()  //
                  ? "true"
                  : "false")
          << "\n";
std::cout << (is_arr<int>()  //
                  ? "true"
                  : "false")
          << "\n";

$ ./main.out | sed '1,/<3/d;/3>/,$d'
true
false

Of course, this is quite a contrived example — we could’ve just used std::is_array directly. The real power of constexpr-if is that it discards the false clause of the if statement.

For example, if we had some generic code that accepted either a pointer or a reference and was supposed to return its value:

template <typename T>
auto get_value(const T& x) {
  if (std::is_pointer_v<T>) {
    return *x;
  } else {
    return x;
  }
}

int x = 0;
int* y = &x;

get_value(x);
get_value(y);

$ make broken3.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken3.o broken3.cpp
broken3.cpp:9:12: error: indirection requires pointer operand ('int' invalid)
    return *x;
           ^~
broken3.cpp:21:3: note: in instantiation of function template specialization 'get_value<int>' requested here
  get_value(x);
  ^
broken3.cpp:11:5: error: 'auto' in return type deduced as 'int *' here but deduced as 'int' in earlier return statement
    return x;
    ^
broken3.cpp:22:3: note: in instantiation of function template specialization 'get_value<int *>' requested here
  get_value(y);
  ^
2 errors generated.
make: *** [Makefile:25: broken3.o] Error 1

It doesn’t work for either case! In the first case (where T = int), it is as if we had the function on the left, and in the second case (T = int*), the function on the right:

int get_value(const int& x) {
  if (false) {
    return *x;
  } else {
    return x;
  }
}

int get_value(const int*& x) {
  if (true) {
    return *x;
  } else {
    return x;
  }
}

Even though the branches are either always-true or always-false, they still need to typecheck — and since int is not a pointer, it cannot be dereferenced. In the second case, we got a complaint about conflicting deduced return types — when the return type is auto, all return statements must agree on the return type, which is not true here.

So, instead of making a function that works for both cases, we made one that works for neither!

If we used constexpr instead, like this:

template <typename T>
auto get_value(const T& x) {
  if constexpr (std::is_pointer_v<T>) {
    return *x;
  } else {
    return x;
  }
}

int x = 69;
int* y = &x;
std::cout            //
    << get_value(x)  //
    << "\n";
std::cout            //
    << get_value(y)  //
    << "\n";

$ ./main.out | sed '1,/<4/d;/4>/,$d'
69
69

This works because in the first instantiation (T = int) of the template, the condition is false, and it’s discarded; the compiler never sees *x, so it works. In the second instantiation (T = int*), the condition is true, so the else branch is discarded; there’s now only one return statement, so there’s no conflict.

Note that for else if statements, you need else if constexpr (...).

2.7.1 Formal specification of constexpr-if

More formally, constexpr if statements are specified to discard the false branch of the if statement, and return statements in the discarded branch are not considered for function return-type deduction.

Furthermore, note that typechecking still applies when you use constexpr-if outside of a templated function; the false branch is still discarded, but since the types are all known, it must still typecheck. For example, the following will fail to compile:

void foo() {
  if constexpr (false) {
    int x = 10;
    int y = *x;
  }
}

Lastly, labels can only jump around within the same constexpr branch, and you can’t use goto to jump into a if-constexpr branch.

2.8 static_assert

One of the things you might have seen us use before without much explanation is static_assert. It is essentially the compile-time equivalent of regular assert, except that the boolean value must be a constant expression (ie. known at compile-time).

You can also pass a message as the second argument, though it is optional. If the condition is false, then an error is issued at compile time, rather than at runtime.

For instance:

constexpr int x = 10 * 20;
static_assert(x < 69, "math");

$ make broken4.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken4.o broken4.cpp
broken4.cpp:6:3: error: static_assert failed due to requirement 'x < 69' "math"
  static_assert(x < 69, "math");
  ^             ~~~~~~
1 error generated.
make: *** [Makefile:25: broken4.o] Error 1

If we tried to use a runtime value, it wouldn’t compile either, but with a different error message:

int x = 10 * 20;
static_assert(x < 69, "math");

$ make broken5.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken5.o broken5.cpp
broken5.cpp:6:17: error: static_assert expression is not an integral constant expression
  static_assert(x < 69, "math");
                ^~~~~~
broken5.cpp:6:17: note: read of non-const variable 'x' is not allowed in a constant expression
broken5.cpp:5:7: note: declared here
  int x = 10 * 20;
      ^
1 error generated.
make: *** [Makefile:25: broken5.o] Error 1

Note that the actual requirement is that the condition is a constant expression — as discussed earlier, this includes constant-initialised const (but not necessarily constexpr) variables.

Another aspect of static_assert that is superior to regular asserts (other than being checked at compile-time) is that they can appear at global (namespace) scope, and in member scope, ie. inside the body of struct definitions. This can let you assert certain invariants on the template parameters to your class.

2.8.1 Using static_assert in templates

In templated code, you might want to assert that the type argument fulfils some criteria of course. Since we learned about constexpr-if just now, you might be tempted to write something like this:

template <typename T>
auto foozle(T x) {
  if constexpr (std::is_pointer_v<T>) {
    return *x;
  } else {
    static_assert(false, "no pointers!");
  }
}

$ make broken6.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken6.o broken6.cpp
broken6.cpp:11:5: error: static_assert failed "no pointers!"
    static_assert(false, "no pointers!");
    ^             ~~~~~
1 error generated.
make: *** [Makefile:25: broken6.o] Error 1

Note that we didn’t even have to call the function — it just always fails! This is because the standard specifies that if no valid specialisation can be generated for a template, then the program is ill-formed¹ — even if the template is not instantiated.

The way to get around this is to make the condition dependent — even if it ends up being always false. For example, this is a common idiom:

template <typename>
constexpr bool always_false = false;

template <typename T>
auto foozle(T x) {
  if constexpr (std::is_pointer_v<T>) {
    return *x;
  } else {
    static_assert(always_false<T>, "pointers only!");
  }
}

int x = 10;
foozle(&x);

If we try to call it with a non-pointer, we get the expected failure:

int x = 0;
foozle(x);

$ make broken7.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken7.o broken7.cpp
broken7.cpp:13:5: error: static_assert failed due to requirement 'always_false<int>' "pointers only!"
    static_assert(always_false<T>, "pointers only!");
    ^             ~~~~~~~~~~~~~~~
broken7.cpp:20:3: note: in instantiation of function template specialization 'foozle<int>' requested here
  foozle(x);
  ^
1 error generated.
make: *** [Makefile:25: broken7.o] Error 1

3 Non-type template parameters (NTTP)

The first addition to templates that we’ll introduce is the ability to use non-type parameters. In the templates we’ve seen so far, the template parameters have always been types — typename T or class T.

C++ allows us to also pass values, and in fact we’ve already seen this for std::array, which takes in both a type (the element type) and a number (the size of the array).

To declare a non-type template parameter, simply use the type that you want in place of typename. For example, the template declaration of std::array might look something like this:

template <typename ElemTy, size_t Length>
class array { /* ... */ };

And to use it, we simply do something like std::array<int, 32> — basically like a normal template with types.

3.1 Deducing array sizes with NTTPs

If you were curious and opened all the boxes, we actually spoilered this in Lecture 1! By using a non-type parameter, we can get the compiler to tell us the size of an array argument:

CppInsights link

template <size_t N>
void print_array(int (&xs)[N]) {
  std::cout << "[ ";
  for (size_t i = 0; i < N; i++) {
    std::cout << (i ? ", " : "")  //
              << xs[i];
  }
  std::cout << " ]\n";
}

int a1[] = {1, 2, 3};
std::cout << "a1 = ";
print_array(a1);

int a2[] = {1, 4, 9, 16, 25};
std::cout << "a2 = ";
print_array(a2);

$ ./main.out | sed '1,/<1/d;/1>/,$d'
a1 = [ 1, 2, 3 ]
a2 = [ 1, 4, 9, 16, 25 ]

If we look at the CppInsights link above, we see two separate instantiations of the template — print_array<3> and print_array<5> — exactly what we would expect if we instantiated a type parameter with different types.

Of course, we can take this further by templating the element type as well:

template <typename T, size_t N>
void print_array(T (&xs)[N]) {
  std::cout << "[ ";
  for (size_t i = 0; i < N; i++) {
    std::cout << (i ? ", " : "")  //
              << xs[i];
  }
  std::cout << " ]\n";
}

std::string a1[] = {"aa", "bb"};
std::cout << "a1 = ";
print_array(a1);

double a2[] = {3.14, 2.71828, 6.9};
std::cout << "a2 = ";
print_array(a2);

$ ./main.out | sed '1,/<2/d;/2>/,$d'
a1 = [ aa, bb ]
a2 = [ 3.14, 2.71828, 6.9 ]

3.1.1 Deducing string lengths

Note that, since string literals are really an array of const char, we can use the same technique to create template functions that know the length of the string at compile time — provided it’s a literal:

template <size_t N>
void lit_strlen(const char (&)[N]) {
  std::cout << "length = "  //
            << N - 1 << "\n";
}

std::string a1[] = {"aa", "bb"};
std::cout << "a1 = ";
print_array(a1);

double a2[] = {3.14, 2.71828, 6.9};
std::cout << "a2 = ";
print_array(a2);

$ ./main.out | sed '1,/<3/d;/3>/,$d'
length = 5
length = 10

An important thing to note is that the length of the array will include the null terminator, so the actual length — the number of characters — will be N - 1.

3.2 Class-type NTTPs

Starting with C++20, we can also pass class types as template parameters; more formally, we can use a type as a non-type template parameter if it falls under one of these categories:

1. lvalue reference type
2. integral type
3. pointer type
4. enumeration type
5. std::nullptr_t
6. floating-point type
7. a class satisfying the LiteralType named requirement (above), and:
   • all base classes and all data members are public and not declared mutable
   • the types of all base classes and all data members are structural types

The categories above are collectively known as structural types. Prior to C++20, floating-point types and classes were not allowed, but now they are :D.

3.2.1 Passing strings in templates

One of the things that people really wanted to do in C++17, but couldn’t do easily, was to pass strings as an NTTP. There were very limited ways that it could be done, but it was quite a pain so we won’t discuss it.

What we can do now in C++20 is to create a simple wrapper class that lets us pass strings around:

template <size_t Len>
struct String {
  constexpr String(const char (&str)[Len]) {
    std::copy(str, str + Len, m_buf);
  }

  template <size_t L2>
  constexpr bool operator==(const String<L2>& s) const {
    return Len == L2  //
           && std::equal(m_buf, m_buf + Len, s.m_buf);
  }

  template <size_t L2>
  constexpr bool operator==(const char (&s)[L2]) const {
    return *this == String<L2>(s);
  }

  char m_buf[Len];
};

Note that we had to make both the constructor and the operator== constexpr, otherwise the class would not be very usable at compile time.

This also shows that we can use templated classes as NTTPs. Then, we can create templated functions that can operate on these strings at compile time:

template <String s>
void foozle() {
  if constexpr (s == "hello") {
    std::cout << "hello to you too\n";
  } else {
    std::cout << "i don't understand\n";
  }
}

foozle<String("hello")>();
foozle<String("aoeu")>();

foozle<"hello">();

$ ./main.out | sed '1,/<4/d;/4>/,$d'
hello to you too
i don't understand
hello to you too

In the last example here, note that we didn’t need to explicitly construct the String — the compiler called the constructor for us! This allows us greater flexibility in writing code that can execute at compile-time, without being overly verbose.

For example, if we look at the godbolt link, the assembly looks something like this:

main:
        push    rbp
        mov     rbp, rsp
        call    void foozle<String<4ul>{...}>()
        call    void foozle<String<6ul>{...}>()
        xor     eax, eax
        pop     rbp
        ret
void foozle<String<4ul>{...}>():
        push    rbp
        mov     rbp, rsp
        movabs  rdi, offset .L.str
        call    puts
        pop     rbp
        ret
void foozle<String<6ul>{...>():
        push    rbp
        mov     rbp, rsp
        movabs  rdi, offset .L.str.1
        call    puts
        pop     rbp
        ret

As we can see, there are no comparisons at runtime! We simply load the string literal into the register, and call puts directly.

4 Template specialisation

Reference: Explicit (full) template specialisation

Sometimes, we might want to customise the behaviour of a templated function for specific types or combination of types. Instead of individually checking each time in the body, we can just specialise the function.

We can rewrite the if constexpr checks above to use specialisation instead:

template <String s>
void bazzle() {
  std::cout << "ich verstehe nicht\n";
}

template <>
void bazzle<"hello">() {
  std::cout << "hello to you too\n";
}

template <>
void bazzle<"bye">() {
  std::cout << "goodbye\n";
}

The caller looks exactly the same:

bazzle<"hello">();
bazzle<"bye">();
bazzle<"aoeu">();

$ ./main.out | sed '1,/<5/d;/5>/,$d'
hello to you too
goodbye
ich verstehe nicht

Now, we can call the correct function directly, without even doing any checks at compile time — the compiler does it for us when performing overload resolution.

Note that there’s another way to specialise function templates other than the explicit (full) specialisation which we used for bazzle<"hello">, which is to (indirectly) specify the type of T via the parameter list:

template <typename T>  // overload 1
void take_pointer(T p) {
  printf("p(1) = %p\n", (void*) p);
}

template <>  // specialisation of overload 1!
void take_pointer(void* p) {
  printf("p(S1) = %p\n", p);
}

Note that specialised templates can have entirely different definitions and thus behaviours — though as part of good API design, they shouldn’t really differ too drastically. Some examples of when specialisation can be useful is to optimise the performance for a specific type, or when a particular value needs special handling because of how it is.

4.1 Overloading function templates

Function templates can also be overloaded, like this:

template <typename T>  // overload 1
void take_pointer(T p) {
  printf("p(1) = %p\n", (void*) p);
}

template <>  // specialisation of overload 1!
void take_pointer(void* p) {
  printf("p(S1) = %p\n", p);
}

template <typename T>  // overload 2
void take_pointer(T* p) {
  printf("p(2) = %p\n", (void*) p);
}

template <typename T>  // overload 3
void take_pointer(const T* p) {
  printf("p(3) = %p\n", (void*) p);
}

Note that this is distinct from specialisation; these are overloads. When resolving a function call, the compiler only considers overloads and the primary template. In this case, overloads 1-3, and not the specialisation.

Only after the primary template is selected does the compiler decide which specialisation to use (in this case, there’s only one).

One key caveat is that the order of definition matters here — especially so because we can overload function templates. The specialisation defined above specialises the first overload!

If we moved it after overload 2, then it would specialise the second overload, and so on.

int x = foo<int, char>(69, 'x');
int y = foo(420, 'q');

template <>
foo<int, char>(int, char) { /* ... */ }

4.2 Function template specificity rules

So, how does the compiler choose which function to call? It decides via overload resolution, which is a very long page.

In short, the idea is that the compiler decides which template is more specific, and chooses that one. In order to see which is more specific, between each pair of function templates F1 and F2, the compiler does the following:

1. set each template parameter in F1 to a unique hypothetical type X_k
2. try to use each X_k to match the parameters of F2, without implicit conversions
3. repeat with F1 and F2 swapped

If, in step 2, F1 can match with F2 but not the other way around, then F2 is more specialised than F1, and vice versa. These set of rules naturally leads to the following behaviour:

• A specific type (eg. int) is more specialised than a template parameter (T)
• T* is more specialised than T, because while X* can match a T, X cannot match a T*
• const T is more specialised than T, because while X can match a const T, the converse is not true

If both F1 and F2 can match each other in step 2, it’s an ambiguous call and it’s an error.

Let’s look at an example:

template <typename T>  // overload 1
void take_pointer(T p) {
  printf("p(1) = %p\n", (void*) p);
}

template <>  // specialisation of overload 1!
void take_pointer(void* p) {
  printf("p(S1) = %p\n", p);
}

template <typename T>  // overload 2
void take_pointer(T* p) {
  printf("p(2) = %p\n", (void*) p);
}

template <typename T>  // overload 3
void take_pointer(const T* p) {
  printf("p(3) = %p\n", (void*) p);
}

const int x = 69;
take_pointer(&x);
take_pointer((void*) &x);

$ ./main.out | sed '1,/<1/d;/1>/,$d'
p(3) = 0x7fffffffebdc
p(2) = 0x7fffffffebdc

In the first call, we call take_pointer with const int*. While it could have chosen overload 1 and deduced T = const int*, it instead chose overload 3 and deduced T = int. This is an example of how the compiler orders function templates by their specificity.

In the second call, we call it with void*. While p(S1) is a perfect match for the argument type, overload 2 is called instead. This is due to the rule we mentioned above — the compiler only considers non-template functions and the “primary” templates (in this case, overloads 1-3) in overload resolution. Only after it chooses a given primary template does it check which specialisation to use (if any).

Between overloads 1-3, overload 2 is the best match, so it is selected; it has no specialisation, so nothing special is done.

Note that the full rules for how this works together with the rest of overload resolution will be covered later (under… overload resolution).

4.3 Specialising classes

Of course, class templates can also be specialised. One of the canonical examples of specialising classes is in the type_traits library. Suppose that we wanted to define a very simple trait — is_int, which is true when the template parameter is an int, and false otherwise.

We can then do something like this:

template <typename T>
struct is_int  //
    : std::false_type {};
template <>
struct is_int<int>  //
    : std::true_type {};

static_assert(is_int<int>::value);
static_assert(!is_int<long>::value);
static_assert(!is_int<char>::value);
static_assert(!is_int<float>::value);

Here, we declared a template class is_int which inherits from false_type in all cases, unless the template parameter is int, in which case it inherits from true_type. Essentially, the trait is “true” for ints and “false” otherwise.

We’ll cover the actual usage of true_type and friends later, but they’re essentially just a struct with a value static member, which is either true or false as their names would suggest.

The important thing here is that we specialised is_int much like we would specialise functions, and that the compiler picked the more specialised struct correctly. This is an explicit specialisation, which is denoted by template <>, in which the full set of template parameters are specified and specialised.

4.4 Partial specialisation (classes and variables)

Reference: Partial template specialisation

Classes (and variables) with more than one template parameter can also be partially specialised, where at least one of the template parameters are left unspecialised (ie. as parameters), and one or more are specialised.

For example, here we have a simple Pair class, and we can specialise it for cases where the first element is int:

template <typename A, typename B>
struct Pair {};

template <typename B>
struct Pair<int, B> {};

The syntax here is similar to an explicit specialisation, just that we also have some template parameters. Of course, the parameters of the partial specialisation cannot be exactly the same as the original template.

For a less contrived example, we can implement an is_array type trait that’s similar to our is_int one. The issue here is that we need to handle all the different possible array element types — which is completely infeasible to do with explicit specialisations only (we’d need to list every single element type — which is potentially limitless).

Instead, we can leave the element type as a template parameter:

template <typename T>
struct is_array  //
    : std::false_type {};

template <typename T>
struct is_array<T[]>  //
    : std::true_type {};

static_assert(!is_array<int>::value);
static_assert(!is_array<char>::value);
static_assert(is_array<int[]>::value);

using P = Pair<int, char>;
static_assert(is_array<P[]>::value);

This would work for all array types, since the element type is itself a template parameter. In fact, this is how many of the type trait templates in the standard library are implemented. If we look at the implementation of std::is_array, we’ll see that this is exactly how it’s implemented.

4.4.1 Partial ordering of partial specialisations

Just like how there is a partial ordering for function template specialisations, there is also a similar set of rules for partial specialisations. This ensures that the compiler will select the correct (more specialised) template when we have multiple specialisations.

Thankfully (kind of?), the rules for ordering here are just to transform each class partial specialisation into a (fictitious) function template, and then use the same rules for function template overload resolution.

First, let’s go back to our pair class, and add another partial specialisation; we also show the equivalent “fictitious function template”:

template <typename A, typename B>
struct Pair2 {
  int x = 1;
};

/* transformed:
    template <typename B> void f(Pair2<int, B>);
*/
template <typename B>
struct Pair2<int, B> {
  int x = 2;
};

/* transformed:
    template <typename A> void f(Pair2<A, char>);
*/
template <typename A>
struct Pair2<A, char> {
  int x = 3;
};

Note that we also added a single field, so we can tell the specialisations apart. The rules themselves are relatively simple:

1. if only one specialisation matches, then that specialisation is used
2. if more than one specialisation matches, then the partial ordering rules are used to determine which specialisation is a better match. As usual, if two or more are equally specific, then it’s ambiguous (an error).
3. if none of the specialisations match, then the original (non-specialised) template is used.

Note that explicit specialisations are preferred over partial specialisations.

Let’s try to instantiate various pair classes now:

Pair2<float, double> a{};
Pair2<int, double> b{};
Pair2<char, double> c{};
Pair2<float, char> d{};

std::cout << "a: " << a.x << "\n";
std::cout << "b: " << b.x << "\n";
std::cout << "c: " << c.x << "\n";
std::cout << "d: " << d.x << "\n";

$ ./main.out | sed '1,/<2/d;/2>/,$d'
a: 1
b: 2
c: 1
d: 3

As we would expect, a uses the primary (unspecialised) template, b matches the first partial specialisation since the first template argument is int, c also uses the primary template, and d uses the second partial specialisation.

Now, what would happen if we tried to instantiate Pair2<int, char>? Would it pick the first specialisation or the second one?

$ make broken.out
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken.o broken.cpp
broken.cpp:17:20: error: ambiguous partial specializations of 'Pair2<int, char>'
  Pair2<int, char> p{};
                   ^
broken.cpp:7:8: note: partial specialization matches [with B = char]
struct Pair2<int, B> {
       ^
broken.cpp:12:8: note: partial specialization matches [with A = int]
struct Pair2<A, char> {
       ^
1 error generated.
make: *** [Makefile:25: broken.o] Error 1

The answer is neither, since it’s ambiguous. Note that instead, if we added a full specialisation for <int, char>, then it will get chosen in this case, and won’t be ambiguous:

template <>
struct Pair2<int, char> {
  int x = 4;
};

Pair2<int, char> e{};
std::cout << "e: " << e.x << "\n";

$ ./main.out | sed '1,/<3/d;/3>/,$d'
e: 4

5 Variadic templates

Reference: Parameter packs

If you’re familiar with C, you might know about its variadic functions like printf and friends, allowing you to pass in any number of arguments in the call.

5.1 Motivation: C’s (bad) variadic functions

Just as an exercise, let’s try to write a type-safe println using C-variadic functions.

void println(const char* fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  // ????????

  va_end(ap);
}

Therein lies the problem — not only is there no way to figure out how many arguments were actually passed in, we don’t even know their types! This is completely unsafe, and the reason that people discourage using something other than a string literal as the format string, because that’s the only way printf can know the types and number of arguments to expect.

Furthermore, we are forced to iterate the parameters at runtime, which can be costly.

5.2 Introduction to variadic templates

This is where variadic templates save the day; we’ve already seen a brief example of them when implementing in-place construction in Lecture 6.

For this section, we’ll implement a simple type-safe alternative to printf that uses variadic templates. Prior to the introduction of variadic templates, we might have done something (cursed) like this:

void println(const char* fmt);

template <typename T1>
void println(const char* fmt, T1&& a1);

template <typename T1, typename T2>
void println(const char* fmt, T1&& a1, T2&& a2);

// ... oh no ...

Of course while this might end up working, it’s definitely not sustainable. What we want is to define a single function that can take in a varying number of arguments.

As we saw before, we can define a variadic template like this:

template <typename... Args>
void println(const char* fmt, Args&&... args);

We put ... after the typename in the template declaration, and in the function parameter list we append ... to the name of the template parameter. Note here that we also used &&, which in this context makes each parameter a forwarding reference.

There’s also one regular parameter — const char* fmt — which will be our format string.

The typename... Args part is known as a template parameter pack, and the Args&&... args part is known as a function parameter pack. A template with at least one parameter pack is known as a variadic template.

Of course, this is not limited to functions — you can use template parameter packs on classes and variables too.

Note that every unique combination of types used to call a variadic function will generate a new, separate instantiation of the function. That is, println('a', 97) and println(98, 'b') will instantiate the function twice; This can be an issue if code size is a concern.

However, this also means that the compiler knows the types of every argument at compile-time, and so it can better optimise the generated code. This is in contrast with C variadics, which can only be operated on at runtime.

5.3 Recursively expanding parameter packs

One big issue in working with parameter packs is that you cannot index into them; this is because each argument in the pack might have a different type (remember, it’s as if each typename were an independent template parameter).

There are two common ways to use them, which we will cover here. The first way, and the only way pre-C++17, is to use recursion to “peel” off one parameter at a time from the parameter pack. We can do this like so:

void println(const char* fmt) {  //
  std::cout << fmt << "\n";
}

template <typename Arg1, typename... Args>
void println(const char* fmt, Arg1&& arg1, Args&&... rest) {
  auto len = strlen(fmt);
  for (size_t i = 0; i < len; i++) {
    if (fmt[i] == '{' && i + 1 < len && fmt[i + 1] == '}') {
      std::cout << std::string_view(fmt, i)  //
                << arg1;
      return println(fmt + i + 2, std::forward<Args>(rest)...);
    }
  }
}

Here, we recursively call println with the “rest” of the arguments. Parameter packs can be empty, so if we call println with at least one argument, we always get the second overload; the first overload just serves as the base case.

Note the use of std::forward to correctly forward the arguments’ value categories through the recursion here, as well as the use of forwarding references (Args&&) to take in the actual values.

The rest of the code is just to handle the simplest parsing of the “format string”, which just looks for {} in the string.

int x = 69;
std::string s = "hello, world";

println("hello, {}, asdf, {}", x, s);

$ ./recursive1.out
hello, 69, asdf, hello, world

One key point to note here is that we used ... to expand the parameter pack. It behaves rather intuitively, with the caveat that its placement affects the expansion you get. We placed it outside of the call to std::forward, causing it to expand to something like this:

// std::forward<Args>(args)... becomes
std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), ...

If we instead mistakenly placed it inside, we would expand to something like this:

// std::forward<Args>(args...) becomes
std::forward<Args>(arg1, arg2, ...)

This wouldn’t work because Args doesn’t get expanded — it doesn’t appear in the expression preceding ..., which is only args.

We can now use this function to print anything that has operator<< defined, like std::string, which is great.

5.4 Fold expressions

Reference: Fold expressions

The other way to deal with parameter packs is to use fold expressions, which essentially applies an operator over every item in the parameter pack.

Let’s start by introducing a helper function that only prints one value:

template <typename Arg>
void print_one(const char*& fmt, size_t& len, Arg&& arg) {
  for (size_t i = 0; i < len; i++) {
    if (fmt[i] == '{' && i + 1 < len && fmt[i + 1] == '}') {
      std::cout << std::string_view(fmt, i) << arg;
      fmt += (i + 2);
      len -= (i + 2);
    }
  }
}

Here, we are taking both the format string (fmt) and the length (len) by reference, which will be important later. We simply do the same checks for {}, then print the preceding format string followed by the value itself.

We then adjust fmt and len to skip the part we already printed (and the {}) — which affects the caller, because they’re references.

Now, let’s look at the actual println function:

void println(const char* fmt) {  //
  std::cout << fmt << "\n";
}

template <typename... Args>
void println(const char* fmt, Args&&... args) {
  auto len = strlen(fmt);
  (print_one(fmt, len, std::forward<Args>(args)), ...);
  std::cout << "\n";
}

That’s it! We simply pass in fmt and len to print_one, do some weird syntax magic, and it works. Note that we still had to define an overload that has no values; if the pack is empty, then the fold expression expands to nothing. We can verify that the output is still the same:

int x = 69;
std::string s = "hello, world";

println("hi");
println("hello, {}, asdf, {}", x, s);

$ ./fold1.out
hi
hello, 69, asdf, 69

Now, let’s look at fold expressions. They have 4 basic forms:

(Pack <op> ...)             // unary right fold
(... <op> Pack)             // unary left fold
(Pack <op> ... <op> init)   // binary right fold
(init <op> ... <op> Pack)   // binary left fold

Here, Pack denotes the name of the parameter pack, and <op> is the operator that we want to fold over. Note that only binary operators can be folded over — even in the unary fold case.

If we let the pack values be a, b, ..., z, these folds would expand to:

(Pack + ...)      =>    (a + (b + (c + (... + (y + z)))));
(... + Pack)      =>    (((((a + b) + c) + ...) + y) + z);
(Pack + ... + 0)  =>    (a + (b + (c + (... + (z + 0)))));
(0 + ... + Pack)  =>    (((((0 + a) + b) + c) + ...) + z);

In our case, we folded over the comma operator , using a unary right fold. This means that the code expands to something like this:

print_one(fmt, len, std::forward<Arg1>(arg1)),
print_one(fmt, len, std::forward<Arg2>(arg2)),
print_one(fmt, len, std::forward<Arg3>(arg3)), ...;

This is why we made it take references, so that subsequent calls to print_one can take the modified state (and further modify it).

Another point to note is that the parameter pack can appear anywhere inside the subexpression that you use in the folded expression, and wherever it appears, the actual value is substituted. This is how we can just use std::forward<Args>(args), and it automatically works.

Finally, fold expressions can sometimes be faster (at runtime) than recursive expansion, simply because there isn’t a recursive call. The compiler is not always able to optimise out the recursive call even if all the types are known, so you should typically prefer to use fold expressions whenever possible.

5.4.1 Other examples of fold expressions

There are other ways we can use fold expressions. For example, if we only wanted to make a function that printed its arguments without any format string capability, we could do this:

template <typename... Args>
void print_stuff(Args&&... args) {
  (std::cout << ...                        //
             << std::forward<Args>(args))  //
      << "\n";
}

$ ./fold2.out
1hello3.1415

Of course the output is a little bad because there’s no spaces, but there’s ways to fix it (:

5.5 sizeof... operator

One small thing you can do is to use sizeof...(pack) to get the number of things in the parameter pack:

template <typename... Args>
void varargs_len1(Args&&... args) {
  std::cout << "got "           //
            << sizeof...(args)  //
            << " arg(s)\n";
}

template <typename... Args>
void varargs_len2(Args&&... args) {
  std::cout << "got "           //
            << sizeof...(Args)  //
            << " arg(s)\n";
}

varargs_len1(10, 20, 30);
varargs_len1();
varargs_len2("aaa");

$ ./misc.out
got 3 arg(s)
got 0 arg(s)
got 1 arg(s)

As you can see, just like normal sizeof, we can use either the template parameter pack (the type, Args) or the function parameter pack (the value, args).

6 Substitution failure is not an error (SFINAE)

Reference: SFINAE

One last technique that we will cover is SFINAE — substitution failure is not an error. First, we must talk about what is substitution, and how it fails.

6.1 Substitution and failures

Types are substituted by the compiler, in:

• all types used in the function type (including parameter and return types)
• all types used in template parameters
• all expressions used in the function type (eg. decltype)
• all expressions used in a template parameter declaration
• all expressions used in the explicit specifier (conditionally explicit)

Substitution happens in lexical order (ie. the order in which the things appear in the source code), and proceeds until the first failure.

A substitution failure happens when any of the types or expressions above would be ill-formed when the given template argument types are substituted. For instance:

template <typename T>
auto foo(const T& x) -> decltype(x.foo()) {
  /* ... */
}

// later...
struct Bar {
  int bar();
};

foo(Bar{});

Here, we tried to use x.foo() in the return type of the function, but the template type (T = Bar) does not have such a member function. In this case, we get a substitution failure.

This only applies to the immediate context of the template declaration — ie. the template parameters, parameter types, and return type. It does not apply inside the function body.

For instance, if we tweak the example above slightly:

template <typename T>
auto foo(const T& x) {
  auto y = x.foo();
  /* ... */
}

Here, the function’s immediate context doesn’t have any substitution failures; if this template is chosen at instantiation time, then it will produce a “real” error that stops compilation, because Bar does not have a foo() method.

6.2 Using SFINAE

What happens when a substitution failure occurs? Well, the compiler simply removes the function that failed substitution from the overload set that is being considered. This means that in order to use SFINAE properly, you usually need at least 2 overloads of a function.

Let’s go back to our foozle example above; supposed that we wanted to make it call the foo() method of the thing we pass in, but if it doesn’t have such a method, it should just print an error message at runtime.

We can make two overloads:

template <typename T>
auto foozle(T x) -> decltype(x.foo()) {
  return x.foo();
}

void foozle(...) {  //
  puts("cannot foo()");
}

struct Foo {
  void foo() {
    puts("foo");
  }
};

struct Bar {
  int x;
};

foozle(10);
foozle(Bar{});
foozle(Foo{});

$ ./main.out | sed '1,/<1/d;/1>/,$d'
cannot foo()
cannot foo()
foo

We get the expected behaviour here. However, you might have noticed that we used ... as the parameter type of the second overload. Why is that? Because SFINAE only works one way — only disabling failing substitutions. It does not only enable succeeding substitutions.

If we were a little naive and tried the “intuitive” second overload:

template <typename T>
void foozle(T) {  //
  puts("cannot foo()");
}

foozle(10);
foozle(Bar{});
foozle(Foo{});

$ make broken1.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken1.o broken1.cpp
broken1.cpp:32:3: error: call to 'foozle' is ambiguous
  foozle(Foo{});
  ^~~~~~
broken1.cpp:17:6: note: candidate function [with T = Foo]
auto foozle(T x) -> decltype(x.foo()) {
     ^
broken1.cpp:23:6: note: candidate function [with T = Foo]
void foozle(T) {  //
     ^
1 error generated.
make: *** [Makefile:25: broken1.o] Error 1

We see that the call with Foo as the argument is ambiguous, because both the first and second overloads are viable, and are equally good. As for why using the C variadic parameter (...) works, we need to get into overload resolution, which is covered below.

6.3 Motivational example of SFINAE

Let’s go back to our println function. It doesn’t really matter which version you use, but we’ll use the one written with fold expressions here. One major motivation of using SFINAE is in cases like this:

// while these are legitimate uses...
println("hello {}", std::string("world"));
println("my fav number is {}", 420);

// if we misuse it,
// we get very long error messages
std::vector<int> v{1, 2, 3};
println("help: {}", v);

$ # This thing prints like
$ make demo-broken.out 2>&1 | wc -l
123
$ # that many lines of error messages

$ make demo-broken.out
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o demo-broken.o demo-broken.cpp
demo-broken.cpp:10:45: error: invalid operands to binary expression ('basic_ostream<char, std::char_traits<char>>' and 'std::vector<int>')
      std::cout << std::string_view(fmt, i) << arg;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^  ~~~
demo-broken.cpp:24:4: note: in instantiation of function template specialization 'print_one<std::vector<int> &>' requested here
  (print_one(fmt, len, std::forward<Args>(args)), ...);
   ^
demo-broken.cpp:37:3: note: in instantiation of function template specialization 'println<std::vector<int> &>' requested here
  println("help: {}", v);
  ^
/usr/lib/llvm-13/bin/../include/c++/v1/cstddef:141:3: note: candidate function template not viable: no known conversion from 'basic_ostream<char, std::char_traits<char>>' to 'std::byte' for 1st argument
  operator<< (byte  __lhs, _Integer __shift) noexcept
  ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:748:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'char' for 2nd argument
operator<<(basic_ostream<_CharT, _Traits>& __os, char __cn)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:781:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'char' for 2nd argument
operator<<(basic_ostream<char, _Traits>& __os, char __c)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:788:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'signed char' for 2nd argument
operator<<(basic_ostream<char, _Traits>& __os, signed char __c)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:795:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'unsigned char' for 2nd argument
operator<<(basic_ostream<char, _Traits>& __os, unsigned char __c)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:809:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'const char *' for 2nd argument
operator<<(basic_ostream<_CharT, _Traits>& __os, const char* __strn)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:855:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'const char *' for 2nd argument
operator<<(basic_ostream<char, _Traits>& __os, const char* __str)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:862:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'const signed char *' for 2nd argument
operator<<(basic_ostream<char, _Traits>& __os, const signed char* __str)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:870:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'const unsigned char *' for 2nd argument
operator<<(basic_ostream<char, _Traits>& __os, const unsigned char* __str)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1055:1: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'const std::error_code' for 2nd argument
operator<<(basic_ostream<_CharT, _Traits>& __os, const error_code& __ec)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:741:1: note: candidate template ignored: deduced conflicting types for parameter '_CharT' ('char' vs. 'std::vector<int>')
operator<<(basic_ostream<_CharT, _Traits>& __os, _CharT __c)
^
/usr/lib/llvm-13/bin/../include/c++/v1/__random/uniform_int_distribution.h:282:1: note: candidate template ignored: could not match 'uniform_int_distribution' against 'vector'
operator<<(basic_ostream<_CharT, _Traits>& __os,
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:802:1: note: candidate template ignored: could not match 'const _CharT *' against 'std::vector<int>'
operator<<(basic_ostream<_CharT, _Traits>& __os, const _CharT* __str)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1038:1: note: candidate template ignored: could not match 'basic_string' against 'vector'
operator<<(basic_ostream<_CharT, _Traits>& __os,
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1046:1: note: candidate template ignored: could not match 'basic_string_view' against 'vector'
operator<<(basic_ostream<_CharT, _Traits>& __os,
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1063:1: note: candidate template ignored: could not match 'shared_ptr' against 'vector'
operator<<(basic_ostream<_CharT, _Traits>& __os, shared_ptr<_Yp> const& __p)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1082:1: note: candidate template ignored: could not match 'bitset' against 'vector'
operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Size>& __x)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1030:11: note: candidate template ignored: requirement 'integral_constant<bool, false>::value' was not satisfied [with _Stream = std::ostream &, _Tp = std::vector<int>]
_Stream&& operator<<(_Stream&& __os, const _Tp& __x)
          ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:1075:1: note: candidate template ignored: could not match 'unique_ptr' against 'vector'
operator<<(basic_ostream<_CharT, _Traits>& __os, unique_ptr<_Yp, _Dp> const& __p)
^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:188:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'std::ostream &(*)(std::ostream &)' for 1st argument
    basic_ostream& operator<<(basic_ostream& (*__pf)(basic_ostream&))
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:192:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'basic_ios<std::basic_ostream<char>::char_type, std::basic_ostream<char>::traits_type> &(*)(basic_ios<std::basic_ostream<char>::char_type, std::basic_ostream<char>::traits_type> &)' (aka 'basic_ios<char, std::char_traits<char>> &(*)(basic_ios<char, std::char_traits<char>> &)') for 1st argument
    basic_ostream& operator<<(basic_ios<char_type, traits_type>&
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:197:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'std::ios_base &(*)(std::ios_base &)' for 1st argument
    basic_ostream& operator<<(ios_base& (*__pf)(ios_base&))
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:200:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'bool' for 1st argument
    basic_ostream& operator<<(bool __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:201:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'short' for 1st argument
    basic_ostream& operator<<(short __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:202:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'unsigned short' for 1st argument
    basic_ostream& operator<<(unsigned short __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:203:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'int' for 1st argument
    basic_ostream& operator<<(int __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:204:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'unsigned int' for 1st argument
    basic_ostream& operator<<(unsigned int __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:205:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'long' for 1st argument
    basic_ostream& operator<<(long __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:206:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'unsigned long' for 1st argument
    basic_ostream& operator<<(unsigned long __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:207:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'long long' for 1st argument
    basic_ostream& operator<<(long long __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:208:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'unsigned long long' for 1st argument
    basic_ostream& operator<<(unsigned long long __n);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:209:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'float' for 1st argument
    basic_ostream& operator<<(float __f);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:210:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'double' for 1st argument
    basic_ostream& operator<<(double __f);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:211:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'long double' for 1st argument
    basic_ostream& operator<<(long double __f);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:212:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'const void *' for 1st argument; take the address of the argument with &
    basic_ostream& operator<<(const void* __p);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:213:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'basic_streambuf<std::basic_ostream<char>::char_type, std::basic_ostream<char>::traits_type> *' (aka 'basic_streambuf<char, std::char_traits<char>> *') for 1st argument
    basic_ostream& operator<<(basic_streambuf<char_type, traits_type>* __sb);
                   ^
/usr/lib/llvm-13/bin/../include/c++/v1/ostream:216:20: note: candidate function not viable: no known conversion from 'std::vector<int>' to 'std::nullptr_t' (aka 'nullptr_t') for 1st argument
    basic_ostream& operator<<(nullptr_t)
                   ^
1 error generated.
make: *** [Makefile:25: demo-broken.o] Error 1

… ok, technically speaking, the large number of error messages is caused by the large number of overloads that operator<< has, but the root cause of these error messages is because C++ is type-checking the contents of print_one<std::vector<int>>, even though it will obviously fail typechecking.

Clearly, this is a situation for just removing the function, and prevent it from instantiating the template in the first place. We can do this using the tools we just covered above:

template <
    typename Arg,
    typename = std::void_t<decltype(std::cout << std::declval<Arg>())>>
void print_one(const char*& fmt, size_t& len, Arg&& arg) {
  for (size_t i = 0; i < len; i++) {
    if (fmt[i] == '{' && i + 1 < len && fmt[i + 1] == '}') {
      std::cout << std::string_view(fmt, i) << arg;
      fmt += (i + 2);
      len -= (i + 2);
    }
  }
}

// blatant misuse
std::vector<int> v{1, 2, 3};
println("help: {}", v);

$ make demo1.out
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o demo1.o demo1.cpp
demo1.cpp:29:4: error: no matching function for call to 'print_one'
  (print_one(fmt, len, std::forward<Args>(args)), ...);
   ^~~~~~~~~
demo1.cpp:37:3: note: in instantiation of function template specialization 'println<std::vector<int> &>' requested here
  println("help: {}", v);
  ^
demo1.cpp:11:6: note: candidate template ignored: substitution failure [with Arg = std::vector<int> &]: invalid operands to binary expression ('std::ostream' (aka 'basic_ostream<char>') and 'std::vector<int>')
void print_one(const char*& fmt, size_t& len, Arg&& arg) {
     ^
1 error generated.
make: *** [Makefile:25: demo1.o] Error 1

Here, we see that there’s a much shorter error message, and the compiler even helpfully tells us what the issue was — that the SFINAE caused this overload to be disabled. Since there were no other valid overloads, the compilation fails.

Using SFINAE, we ensured that print_one is only defined if std::cout << x is well-formed (ie. it compiles correctly), which means that an operator<< is present for the type we have.

6.3.1 Moving the check to println itself

One other solution would be to move the check to println itself, which we can do in a very similar way:

template <typename... Args,
          typename =
              std::void_t<decltype(std::cout << std::declval<Args>())...>>
void println(const char* fmt, Args&&... args) {
  auto len = strlen(fmt);
  (print_one(fmt, len, std::forward<Args>(args)), ...);
  std::cout << "\n";
}

$ make demo2.out
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o demo2.o demo2.cpp
demo2.cpp:37:3: error: no matching function for call to 'println'
  println("help: {}", v);
  ^~~~~~~
demo2.cpp:26:6: note: candidate template ignored: substitution failure [with Args = <std::vector<int> &>]: invalid operands to binary expression ('std::ostream' (aka 'basic_ostream<char>') and 'std::vector<int>')
void println(const char* fmt, Args&&... args) {
     ^
demo2.cpp:18:6: note: candidate function not viable: requires single argument 'fmt', but 2 arguments were provided
void println(const char* fmt) {  //
     ^
1 error generated.
make: *** [Makefile:25: demo2.o] Error 1

Here, we’re taking advantage of the fact that void_t itself takes in any number of template arguments; we now just check that all of them have operator<< defined, taking care to put the ... in the right place (after the decltype).

This solution might be more desirable because the error message directly pinpoints the caller of println, rather than an implementation detail print_one which might be deep inside some of your library code.

6.4 Using enable_if

Reference: std::enable_if

What if we wanted to SFINAE away² the function based on an arbitrary condition, not just “does it have such-and-such method” or “is this expression well-formed”? Well, the standard library has just the type for us — std::enable_if.

Its implementation is actually quite simple, and you can implement it yourself:

template <bool Cond, typename T = void>
struct enable_if {};

template <typename T>
struct enable_if<true, T> {
  using type = T;
};

It uses partial specialisation to work; if the condition is true, then we choose the partial specialisation, and we get the type nested type. If the condition is false, then we don’t get the nested type. Now, we can apply the same SFINAE concepts we saw before; if ::type doesn’t exist, we get SFINAE and the overload is discarded.

The type nested type is the second template parameter, which is defaulted to void; you can also specify it if it needs to be an actual type (depending on where you use it).

In fact, this is the basis of how type_traits work, though we’ll look deeper into those later.

There are a few places we can put enable_if, and we’ll go through all of these.

6.4.1 enable_if in the return type

One place we can use enable_if is in the return type of functions. For example:

template <typename T>
std::enable_if_t<  //
    std::is_integral_v<T>,
    T>
square(T x) {
  return x * x;
}

auto x = square(10);
auto y = square(20UL);
std::cout << "x = " << x    //
          << ", y = " << y  //
          << "\n";

Note that this is one case where we have to specify the second template parameter (well, if we wanted the function to return something other than void).

You can use this placement for most functions (even if they return void), but there are some where it’s not possible:

• constructors (they don’t have a return type)
• conversion operators (you can’t specify the return type)

Note that if you need the enable_if condition to depend on one of the parameter types (or values), you can use the trailing return type declaration syntax, which we’ve seen above:

template <typename T>
auto cube(T x) -> std::enable_if_t<std::is_integral_v<decltype(x)>, T> {
  return x * x * x;
}

(Note that this is quite contrived, since decltype(x) is exactly T).

6.4.2 enable_if as a parameter type

The second place you can use enable_if is in the parameter type. This is often used together with a default parameter, since in most cases we don’t really care about the actual value.

Of course, you are free to use enable_if to declare a “legit” parameter. Otherwise, one typical idiom is to make a default argument of void* type defaulted to nullptr:

template <typename T>
auto pow(T x, T n, std::enable_if_t<std::is_integral_v<T>>* = nullptr) {
  T ret = 1;
  for (T i = 0; i < n; i++)
    ret *= x;
  return ret;
}

Again, there are some situations where you cannot use this:

• conversion operators (they have no parameters)
• operators with a fixed number of parameters (eg. *, --)

6.4.3 enable_if as a template parameter

Finally, the last place you can use enable_if is in the template parameter itself. Like with function parameters, this is typically done as a defaulted parameter, like so:

template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
auto half(T x) {
  return x / 2;
}

This is generally the most flexible, since you can make any of the functions (constructors, conversion operators) templated. Note that we did not need to actually name the parameter here; since we don’t use it in the body, giving it a name is mostly pointless.

There is another way to use enable_if as a template parameter, which is to make it the type of a NTTP, like so:

template <typename T, std::enable_if_t<std::is_signed_v<T>, int> foo = 0>
auto quarter(T x) {
  return x / 4;
}

Here, we used the second (usually defaulted to void) parameter of enable_if to make an integer NTTP that’s defaulted to 0. This works in much the same way as the method above, but with a few benefits — which we’ll discuss immediately below.

6.5 Problems with enable_if

As much as enable_if (or more generally, SFINAE) is quite a powerful construct, there are still some issues that you need to pay attention to in order to use enable_if correctly.

6.5.1 Duplicate definitions

The first issue is that two function templates with different defaulted template parameters are not considered distinct; they are not part of the function’s signature. For instance, if we had these two functions, the compiler would yell at us:

template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
auto square(T) {
  /* ... */
}

template <typename T, typename = std::enable_if_t<std::is_array_v<T>>>
auto square(T) {
  /* ... */
}

$ make broken2.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken2.o broken2.cpp
broken2.cpp:11:34: error: template parameter redefines default argument
template <typename T, typename = std::enable_if_t<std::is_array_v<T>>>
                                 ^
broken2.cpp:6:34: note: previous default template argument defined here
template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
                                 ^
broken2.cpp:12:6: error: redefinition of 'square'
auto square(T) {
     ^
broken2.cpp:7:6: note: previous definition is here
auto square(T) {
     ^
2 errors generated.
make: *** [Makefile:25: broken2.o] Error 1

This is because we have essentially declared two functions that are equivalent. Note that the specific wording in the standard means that defaulted parameters are not considered when determining whether two templates are equivalent.

One way to fix this is to use the second method with non-type template parameters instead, like this:

template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
auto rectangle(T, T) {
  /* ... */
}

template <typename T, std::enable_if_t<std::is_enum_v<T>, int> = 0>
auto rectangle(T, T) {
  /* ... */
}

This works because now, the parameters have different types, so they are not equivalent. Note that while the “real” type of both NTTPs ends up being int, their actual type is still std::enable_if<...>::type, which is not the same since the arguments to enable_if are still distinct.

6.5.2 Ambiguous overloads

As mentioned above, enable_if only serves to disable overloads, and doesn’t say “only enable this overload”. This means that if you have multiple SFINAE-ed overloads that are not completely mutually exclusive, then it’s possible to get ambiguity errors.

For example, if we define two functions that happen to have some overlap:

template <typename T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
auto square(T x) {
  return x * x;
}

template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
auto square(T x) {
  return x * x;
}

// later...
square(10);

$ make broken3.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken3.o broken3.cpp
broken3.cpp:21:3: error: call to 'square' is ambiguous
  square(10);
  ^~~~~~
broken3.cpp:7:6: note: candidate function [with T = int, $1 = 0]
auto square(T x) {
     ^
broken3.cpp:12:6: note: candidate function [with T = int, $1 = 0]
auto square(T x) {
     ^
1 error generated.
make: *** [Makefile:25: broken3.o] Error 1

Here, the issue was that the set of types fulfilling is_arithmetic and is_integral have a non-empty intersection — like int that we use. This only becomes a problem when you try to call the function with a type that results in ambiguity, so it might not be immediately apparent that there’s a bug here.

6.5.3 enable_if cannot be used to disable this declaration

One of the cryptic errors that you might face when using enable_if is this one:

$ make broken4.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o broken4.o broken4.cpp
In file included from broken4.cpp:3:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/iostream:37:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/ios:214:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/__locale:15:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/string:520:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/__functional_base:15:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/__functional/invoke.h:14:
In file included from /usr/lib/llvm-13/bin/../include/c++/v1/__functional/weak_result_type.h:16:
/usr/lib/llvm-13/bin/../include/c++/v1/type_traits:550:78: error: no type named 'type' in 'std::enable_if<false>'; 'enable_if' cannot be used to disable this declaration
template <bool _Bp, class _Tp = void> using enable_if_t = typename enable_if<_Bp, _Tp>::type;
                                                                             ^~~
broken4.cpp:9:29: note: in instantiation of template type alias 'enable_if_t' requested here
  template <typename = std::enable_if_t<std::is_same_v<T, int>>>
                            ^
broken4.cpp:26:23: note: in instantiation of template class 'SimpleVector<float>' requested here
  SimpleVector<float> ys{};
                      ^
1 error generated.
make: *** [Makefile:25: broken4.o] Error 1

The offending code was this:

template <typename T>
struct SimpleVector {
  template <typename = std::enable_if_t<std::is_same_v<T, int>>>
  SimpleVector(T x) {
    // do something
    std::cout << "x = " << x << "\n";
  }

  SimpleVector(...) {  //
    std::cout << "...\n";
  }
  // ... the rest of it ...
};

// later...
SimpleVector<float> ys{};

The problem here is similar to the one we faced when doing static_assert — here, the enable_if did not depend on any template parameters, so at the point of instantiation, SFINAE does not apply. We need the template parameter to be on the constructor itself in order for this to work.

One way to get around this is to create a template parameter and default it, like so:

  template <typename T2 = T,
            typename = std::enable_if_t<std::is_same_v<T2, int>>>
  SimpleVector(T x) {
    // do something
    std::cout << "x = " << x << "\n";
  }

If we run it, we get the expected output (calling the second constructor):

SimpleVector<int> xs{10};
SimpleVector<float> ys{10};

$ ./not-broken5.out
x = 10
...

6.6 Constraining variadic templates to have uniform types

One common scenario is wanting to get the type-safety of C++ variadic templates, but not wanting each argument to be a possibly different type.

Unfortunately, the following isn’t quite possible:

void foo(int... ints) { /* ... */ }

While you can make a variadic template of only int by using non-type parameters like so:

template <int... Ints>
void foo() { /* ... */ }

This limits them to being constant expressions, which is usually undesirable. Instead, what we can do is to use our new SFINAE tricks to ensure that the function is not considered if the types differ.

First, since std::is_same only takes in two types, we need to make some helpers that let us check if all the types we have are the same:

template <typename T>
consteval bool is_same() {
  return true;
}

template <typename T1, typename T2, typename... Ts>
consteval bool is_same() {
  return std::is_same_v<T1, T2> && is_same<T2, Ts...>();
}

Note that we make use of the std::is_same type trait here (explained more below), as well as a base case overload with only one template argument (a type is the same as itself). We make these constexpr so that they can be used in the condition of an enable_if.

Now we can write the actual function. In this case, let’s say we want to make a function that only accepts integers:

template <typename... Args>
auto print_ints(Args&&... values)
    -> std::enable_if_t<is_same<int, Args...>()> {
  ((std::cout << values << ' '), ...);
}

Now we can call it with any number of integers:

print_ints(69, 420);
print_ints(1, 2, 3, 4);

$ ./misc2.out
69 420 1 2 3 4 10 20 10 20 a b c

If we try to call it with some values that are not all integers:

clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o misc2-broken.o misc2-broken.cpp
misc2-broken.cpp:28:3: error: no matching function for call to 'print_ints'
  print_ints(69, 420, 'a');
  ^~~~~~~~~~
misc2-broken.cpp:20:6: note: candidate template ignored: requirement 'is_same<int, int, int, char>()' was not satisfied [with Args = <int, int, char>]
auto print_ints(Args&&... values)
     ^
1 error generated.
make: *** [Makefile:25: misc2-broken.o] Error 1

We even get a nice error message!

Furthermore, we can also extend this so that it can take in any T, not just int:

template <typename T, typename... Args>
auto print_stuff(Args&&... values)
    -> std::enable_if_t<is_same<T, Args...>()> {
  ((std::cout << values << ' '), ...);
}

Of course, in this case you need to manually specify the T when calling print_stuff.

7 Type traits & the metaprogramming library

Reference: Metaprogramming library

You might have noticed along the way that we’ve been using a lot of decltype, is_integral, is_pointer, and other such things without really explaining what they are. Well, now we will explain what they are.

We can group the metaprogramming library into a few groups:

• type categories
• type properties
• type relations
• type transformations

These are also known as the “type traits”, since they can be used to discern the traits of a type.

7.1 Overview of common type traits

We won’t list all of them (just go to the cppreference page for that), but we’ll cover some of the more useful and important traits.

7.1.1 Type categories

These are themselves separated into primary categories and composite categories. The primary ones are things like is_enum, is_integral, is_pointer, etc., and they let you test for the “primary category” of a given type. Note that some of them are not possible to implement yourself, because they rely on compiler support. For example, there’s no mechanism to determine whether a given type is an enumeration or not.

The composite categories are simply combinations of the primary ones:

• is_reference checks is_lvalue_reference || is_rvalue_reference
• is_arithmetic checks is_integral || is_floating_point
• etc.

7.1.2 Type properties

These check the properties of the type; a few useful examples are is_const, is_trivial, is_signed, etc. A subcategory of type properties are the traits that let you check the supported operations on a given type.

Those traits are most useful when writing generic container classes. For instance, you might want to use one implementation if the element type is copy assignable, and another when it is not. These traits also let you check whether the given operation is guaranteed not to throw an exception.

A few useful examples:

• is_copy_assignable / is_trivially_copy_assignable / is_nothrow_copy_assignable
• is_move_constructible / is_trivially_move_constructible / is_nothrow_move_constructible
• is_swappable / is_nothrow_swappable

7.1.3 Type relations

These let you check the relationship between two types. The most useful ones are:

• is_same
  checks if two types are the same
• is_base_of
  checks if one type is a base class of the other
• is_convertible
  checks if one type is convertible from the other
• is_invocable
  checks if the type (function or function object) is invocable with the given arguments

7.1.4 Type transformations

The last category lets you transform (modify) an input type to produce an output type. Common examples include:

• add_lvalue_reference / add_rvalue_reference / remove_reference
  add or remove references
• add_cv / add_const / … / remove_cv / remove_const / …
  add or remove const-volatile (cv) qualifiers
• remove_cvref
remove_reference followed by remove_cv
• common_type
  determine a common type that all input types can be converted to
• decay
  performs decay as-if passing a argument by value (array-to-pointer, etc.)

7.2 Useful utility traits

7.2.1 std::true_type and std::false_type

While std::true_type and std::false_type are not exactly type traits, they are quite useful when implementing traits of your own. Basically, in the true case, you should inherit from true_type, and in the false case, you should inherit from false_type. This just saves you the trouble of making your own value member.

For instance:

template <typename T>
struct is_foozle : std::false_type {};

template <>
struct is_foozle<Foozle> : std::true_type {};

7.2.2 std::void_t

We’ve already used this above; basically, the definition looks like this:

template <typename...>
struct void_t {};

It takes in any number of type arguments, and is essentially an easy way to check whether all of the arguments you give it are well-formed. In fact, that’s exactly how we used it above.

7.3 decltype

Another thing you might have seen us use without much explanation is decltype. As the name might suggest, it allows you to get the type of the expression that you pass in.

For instance, decltype(1 + 2) would be int. You can use decltype where a type would normally be expected, and we’ve seen some use of it in type traits and SFINAE already.

This is a valid (but weird) use of decltype, for instance:

template <typename T>
void foo(T x) {
  decltype(x) y{};
}

7.3.1 decltype(x) vs decltype((x))

One important caveat here is the importance of an extra set of parentheses when using decltype. If we take this piece of code:

int x = 10;
static_assert(std::is_same_v<decltype(x), int>);
static_assert(std::is_same_v<decltype((x)), int&>);

We see that decltype(x) resolves to int, but decltype((x)) resolves to int&? What is this insanity?

The reason is that without the extra parentheses, we are saying “get the type that the name x was declared with”. Since we wrote int x = ..., then decltype(x) = int.

With the extra parentheses however, we are now saying “get the type of the expression (x), and make it a reference depending on its value category”. As we covered in a previous lecture, the value category of a variable name as an expression is always an lvalue, so this is why we get an lvalue reference here.

Specifically, the rules are:

1. if the argument is an unparenthesised identifier expression, the type is whatever the actual type of the variable is
2. otherwise, given an expression of type T:
   • if the value category is an lvalue, return T&
   • if the value category is an xvalue, return T&&
   • if the value category is a prvalue, return T

7.4 std::declval

You can think of std::declval as the cousin of decltype; instead of giving you the type of something, it magically constructs a value of a given type — even if the type is not constructible.

One typical use-case is when declaring (defaulted) template parameters that need to depend on previous parameters, like so:

template <typename T,
          typename = std::enable_if_t<
              std::is_same_v<decltype(std::declval<T>().foo()), int>>>
void kektus() {
  /* ... */
}

Here, we want to check that T has a method foo that returns int. What we might be tempted to do is something like decltype(T{}.foo()), but this might not work if T is not default-constructible for any reason. By using std::declval, we don’t even need to call any constructors and we can magically get a value. As you can imagine, this is usually useful when we want to check for methods.

Of course, you can’t actually call it! It’s only usable in unevaluated contexts like inside a decltype, because it can’t actually construct a “real” value for you.

7.5 Using type traits

Now that we know some of the common type traits, we need to know how to use them. The traits usually come in two flavours: they “produce” either a type or a value (typically a bool).

7.5.1 Value-producing traits

Let’s cover the value-producing ones first. For instance, we might want to check whether a given type is an integral type:

template <typename T>
void foo() {
  if constexpr (std::is_integral<T>::value) {
    std::cout << "T is an integral\n";
  } else {
    std::cout << "T is not an integral\n";
  }
}

struct Foo {
  int x;
};
foo<int>();
foo<float>();
foo<Foo>();

$ ./main.out | sed '1,/<1/d;/1>/,$d'
T is an integral
T is not an integral
T is not an integral

Here, we instantiated is_integral with the type T, and used the value static data member as the “output” — which is either true or false.

This is a little verbose (especially with the extra ::value), so in C++17 we can do this instead:

if constexpr (std::is_integral_v<T>) {
  // ...
}

In fact, this is the form that should be most familiar, since most of our prior examples were of this form. As we can see, we simply use _v instead of ::value. The definition of these helpers is actually quite simple:

template <typename T>
inline constexpr bool is_integral_v = std::is_integral<T>::value;

7.5.2 Type-producing traits

The other class of traits are those that produce types like the type-transforming traits, eg. remove_reference. For example, let’s revisit our simple square function that we used enable_if to SFINAE away earlier:

template <typename T,
          typename = typename std::enable_if<std::is_integral_v<T>>::type>
T square(T x) {
  return x * x;
}

Well, this is definitely one way to do it. Note that because type is a dependent type in this context, we have to manually specify typename before naming the type so that the compiler knows that it should expect a type.

This was not necessary for ::value because by default, the compiler assumes that dependent names refer to values.

Of course, just like the _v helpers for value-producing traits, we also have the similar _t helpers for type-producing traits. In fact, we’ve already them before:

template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
T square(T x) {
  // ...
}

Again, their implementation is quite trivial:

template <bool Cond, typename T = void>
using enable_if_t = typename std::enable_if<Cond, T>::type;

Because of the way C++’s parsing works, the compiler needs to know whether something is a type or a value when it encounters it; because enable_if<T>::type is a dependent name, the compiler doesn’t know, and we had to use typename. For this _t case, it would already know that it refers to a type, because it was declared with using, so typename is unnecessary.

7.6 Dependent names

More formally, dependent names are names that depend on a template parameter. In particular, types and expressions may depend on template parameters — either type parameters or non-type parameters.

These are some common cases of dependent names appearing:

template <typename T>
struct Foo {};

template <typename T>
struct Bar : Foo<T> {               // Foo<T> is a dependent name
  typename Foo<T>::type* asdf = 0;  // Foo<T>::type is a dependent name
  int x = Foo<T>::value;            // Foo<T>::value is a dependent name
};

There are two common situations where we run into dependent names.

7.6.1 Dependent types

We’ve already seen this situation before when using enable_if<T>::type — we had to explicitly specify typename, like so:

template <bool Cond, typename T>
using disable_if_t = typename std::enable_if<not Cond, T>::type;

7.6.2 Dependent templates

The other common situation is when we have a dependent name and we want to use a template. For instance:

template <typename T>
struct Base {
  template <typename U>
  constexpr void uwu(U u) {
    std::cout << "based? based on what?\n";
    std::cout << "based on " << u << "\n";
  }
};

template <typename T>
constexpr int owo() {
  Base<int> b1{};  // b1 does not have a dependent type
  Base<T> b2{};    // b2 has a dependent type

  b1.uwu<int>(1);           // ok, no `template` needed
  b2.template uwu<int>(2);  // `template` is needed

  return 0;
}

In the function, we make two variables, one with type Base<int>, and one with Base<T> — the second one has a dependent type (depending on the template parameter T).

When we call b1.uwu(), since the type of b1 is already known, the compiler knows that uwu is a template function, and can correctly parse the explicit template arguments uwu<int>.

In the second case however, the type of b2 is dependent; in order to prevent the compiler from parsing the < after uwu as a less-than operator (since uwu could be a non-static data member), we use the template keyword.

7.7 Unevaluated contexts

The arguments of the operators sizeof, decltype, noexcept, as well as the contents of requires clauses, are considered unevaluated contexts, which means that the contents are only used for their compile-time properties. This means that, for example, the following code will not print anything:

auto x = sizeof(std::cout << "hello");

We previously mentioned that std::declval can only be used in such a context — using it in a “normal” (ie. evaluated) context will trigger a compile error.

8 Concepts

Earlier, we showed how enable_if can be used wrongly when the conditions used to enable a set of overloads are not mutually exclusive.

However, if we adapt the example to use C++20 concepts, we’ll see that it just works, even though the constraints overlap:

template <typename T>
requires std::integral<T> || std::floating_point<T>
auto square(T x) {
  return x * x;
}

template <typename T>
requires std::integral<T>
auto square(T x) {
  return x * x;
}

// later...
square(10);   // this calls 2nd defn
square(1.0);  // this calls 1st defn

$ make -B subsumption.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o subsumption.o subsumption.cpp
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable    subsumption.o   -o subsumption.out

So that illustrates one of the major motivations behind concepts. On top of making it syntactically much easier to customise behaviour, (requires is much nicer than std::enable_if), it also makes many other corner cases Just Work.

In the rest of this section, we’ll cover both the language and library aspects of C++ concepts.

8.1 Basic usage

Let’s start with a simple example and breakdown.

// Using the `concept` keyword,
// we can declare a new concept
template <size_t I>
concept IsOdd = I % 2 == 1;

// Concepts are *very similar*
// to compile time booleans
template <size_t I>
constexpr bool IsOddBoolean  //
    = I % 2 == 1;

// But we'll see later that
// there are some differences

// We can now add requires clauses
// to declarations and definitions
// to constrain them

// Here, we constrain one definition
// to only become active when the I
// template parameter is odd
template <size_t I>
requires(IsOdd<I>)  //
    bool is_odd_comptime() {
  return true;
}

// And here, we constrain the other
// to only become active when the I
// template parameter is even
template <size_t I>
requires(!IsOdd<I>)  //
    bool is_odd_comptime() {
  return false;
}

Overall, it’s just a better SFINAE.

8.2 Shorthand constrained template parameters

Instead of templating over a typename T and then constraining it with a concept, we can alternatively just write constraint T, like so:

template <typename T>
requires std::integral<T>
void f(T x) {
  ++x;
}

// Alternatively:
template <std::integral T>
void f(T x) {
  ++x;
}

template <typename T>
requires std::convertible_to<T, int>
void f(T x) {
  x + 1;
}

// Alternatively:
// T is prepended at the front of
// the list of template arguments
template <std::convertible_to<int> T>
void f(T x) {
  x + 1;
}

Note the way that we left out the angle brackets for std::integral, and the way that std::convertible_to<int> is missing a template argument. The template parameter being constrained is effectively prepended to the list of template arguments and then the resulting expression is used as the constraint.

8.3 requires expressions

Reference: Requires expression

Using type_traits to make new concepts is possible but very annoying most of the time, especially when we usually just want to check for basic things like whether expressions are well formed.

Using requires expressions, it’s much easier to create new concepts. They look like this:

requires (<similar to function parameters>) {
  // ... requirements go here ...
}

and we can then put a variety of stuff inside.

8.3.1 Basic requirements

For example, we might want to create a concept for whether a type can be printed via std::ostream. In that case, we can make a concept like so:

template <typename T>
concept Printable1 = requires (std::ostream& os, T obj) {
  os << obj;
  // Simply checks that the above expression would compile
};

If we also want to check that the type of the expression is what we expect, we can use the following syntax:

template <typename T>
concept Printable2 = requires (std::ostream& os, T obj) {
  // { ... } -> concept
  // checks that ... is valid
  // AND that the resulting type satisfies the concept

  { os << obj } -> std::same_as<std::ostream&>;
  // Again note that `std::same_as` is missing a template argument,
  // the same rules apply as the constrained template parameter case
  // and the return type is prepended to the start,
  // i.e. this is similar to adding the following constraint:
  //   std::same_as<decltype((os << obj)), std::ostream&>
};

The thing inside { } must be an expression, even though the braces might suggest that it’s a normal block! That is, the following is invalid:

requires(T a, U b) {
  { a + b; a - b } -> int;
}

One reason that the braces are required might be that for some expression like x, a trailing -> could be interpreted as a member access operator, whereas the addition of braces here can allow the parser to parse this unambiguously.

8.3.2 Type requirements

What about concepts like the iterator concepts? For example, we might want to check that a type contains all the member types required to count as an Iterator. In this case, we use typename <expr> for the requirement.

template <typename T>
concept HasIteratorTraits = requires {
  typename std::iterator_traits<T>::difference_type;
  typename std::iterator_traits<T>::reference;
  typename std::iterator_traits<T>::pointer;
  typename std::iterator_traits<T>::iterator_category;
};

8.3.3 Nested requirements

One very useful property of requires expressions is that they give us access to variables of a certain type, so we can easily build up expressions with them. We can then use this to build even bigger concepts that continue to have these variables in scope.

For example, the earlier Printable example could be rewritten:

template <typename T>
concept Printable3 = requires (std::ostream& os, T x) {
  os << x;
  requires std::same_as<decltype((os << x)), std::ostream&>;
};

and in this case the nested requirement came in handy as it allowed us to easily access the return type of os << x.

While this was a little redundant in the earlier example, this can come in handy when we need to append the return type of an expression to a concept, or use the return type in the middle of a larger concept, rather than merely prepending it.

template <typename T>
concept IncrementAndMakeString_able = requires (T x) {
  ++x;

  // Here, we want to *append* the return type of operator++
  // so we know if a std::string can be constructed from a `++x`.
  requires std::constructible_from<std::string, decltype((++x))>;
};

8.4 The requires requires pattern

Since requires defines a concept and requires specifies a constraint, we can use both together to define a concept then immediately apply it to constrain a definition.

template <typename It>
requires requires(It it) { ++it; }
It naive_advance(It it, size_t n) {
  while (n != 0) {
    --n;
    ++it;
  }
  return it;
}

Generally, named concepts are preferred especially because they work better with constraint subsumption, which we discuss below.

8.5 Further improving println with concepts

Let’s look at our println function one last time. We previously used SFINAE to disable the function if any of the types passed in were not printable. However, the error message is still a little obtuse, and we would like to make it very clear what the problem is.

We can do that with concepts, and specifically with the shorthand syntax we discussed above.

First, let’s make a concept that represents being Printable:

template <typename T>
concept Printable = requires(std::ostream& os, T x) {
  os << x;
};

Next, we use the shorthand syntax to ensure that all the template arguments satisfy the Printable concept:

template <Printable... Args>
void println(const char* fmt, Args&&... args) {
  auto len = strlen(fmt);
  (print_one(fmt, len, std::forward<Args>(args)), ...);
  std::cout << "\n";
}

Of course, if we use it, it still works as expected:

int x = 69;
std::string s = "hello, world";

println("hi");
println("hello, {}, asdf, {}", x, s);

$ ./println.out
hi
hello, 69, asdf, 69

The real test is when we try to print something that isn’t printable. We’ll use the same code snippet (printing a std::vector):

$ make println-broken.target
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable   -c -o println-broken.o println-broken.cpp
println-broken.cpp:38:3: error: no matching function for call to 'println'
  println("help: {}", v);
  ^~~~~~~
println-broken.cpp:30:6: note: candidate template ignored: constraints not satisfied [with Args = <std::vector<int> &>]
void println(const char* fmt, Args&&... args) {
     ^
println-broken.cpp:29:11: note: because 'std::vector<int> &' does not satisfy 'Printable'
template <Printable... Args>
          ^
println-broken.cpp:11:6: note: because 'os << x' would be invalid: invalid operands to binary expression ('std::ostream' (aka 'basic_ostream<char>') and 'std::vector<int>')
  os << x;
     ^
println-broken.cpp:25:6: note: candidate function not viable: requires single argument 'fmt', but 2 arguments were provided
void println(const char* fmt) {  //
     ^
1 error generated.
make: *** [Makefile:25: println-broken.o] Error 1

While the errors are longer, they are more explicit — std::vector does not satisfy the constraints, specifically Printable, because os << x would be invalid.

8.5.1 Constraining variadic templates to have uniform types (part 2)

Since we’re talking about variadic templates, we can revisit our print_ints and print_stuff functions from before. Remember how we had to make some helper functions and use enable_if to achieve our goals?

template <typename T>
consteval bool is_same() {
  return true;
}

template <typename T1, typename T2, typename... Ts>
consteval bool is_same() {
  return std::is_same_v<T1, T2> && is_same<T2, Ts...>();
}

template <typename... Args>
auto print_ints(Args&&... values)
    -> std::enable_if_t<is_same<int, Args...>()> {
  ((std::cout << values << ' '), ...);
}

With concepts, we can implement this in a better way:

template <std::same_as<int>... Args>
void print_ints2(Args&&... values) {
  ((std::cout << values << ' '), ...);
}

By using same_as<int> to declare template parameter pack, we’re effectively constraining each (expanded) template parameter to satisfy the same_as<int> concept (recalling that the template is prepended to the argument list, making same_as<T1, int> etc.).

We can use a similar idea to extend this for print_stuff in much the same way as we did for the original:

template <typename T, std::same_as<T>... Args>
void print_stuff2(Args&&... values) {
  ((std::cout << values << ' '), ...);
}

Of course, the error messages are nicer as well, as expected of concepts.

8.6 Constraint subsumption

Reference: Partial ordering of constraints

In a previous lecture, we showed how we can use constraints to implement customised range-based insert_back for our SimpleVector class that made use of the iterator concepts.

template <typename InputIt>
// CONSTRAINT A
requires std::input_iterator<InputIt>
void insert_back(InputIt begin, InputIt end) {
  // DEFINITION A
}

template <typename ForwardIt>
// CONSTRAINT B
requires std::forward_iterator<ForwardIt>
void insert_back(ForwardIt begin, ForwardIt end) {
  // DEFINITION B
}

template <typename RandomIt>
// CONSTRAINT C
requires std::random_access_iterator<RandomIt>
void insert_back(RandomIt begin, RandomIt end) {
  // DEFINITION C
}

However, what would happen if we passed in an iterator that satisfies the constraints for more than one definition? We saw that it would pick the “better” one:

ForwardIt it1, it2;
v.insert_back(it1, it2);

This call site satisfies the constraints for both definition A and B. In this case, we can say that there are two viable candidates. However, the constraint for definition A is std::input_iterator, while the constraint for definition B is std::forward_iterator. Because constraint A subsumes constraint B, definition B is considered “better” than definition A. As a result, this call site invokes definition B.

The reason why constraint B subsumes constraint A is because C++ is able to prove that whenever constraint B is satisfied, constraint A is satisfied. This makes sense, as every std::forward_iterator is also a std::input_iterator.

For the PL / AI / Algo nerds, rest assured that C++ is not solving SAT in the general case. It is simply following a dumb algorithm that handles the most obvious cases in a reasonably short amount of time, like the above example with iterator concepts.

Unfortunately for the same nerds, you’ll find that the description of the algorithm described on cppreference is still exponential time, when naively implemented. I don’t have a clue whether an efficient algorithm exists for this, but please tell me if you know. Thanks.

For normal people, it suffices to know that the following works:

template <typename T>
concept X = ...;

template <typename T>
concept Y = ...;

template <typename T>
concept A = X<T> && Y<T>;

template <typename T>
concept B = X<T>;

// In this case, A subsumes B
// because B has a subset of
// the clauses in A

template <typename T>
concept C = X<T> || Y<T>;

template <typename T>
concept D = X<T>;

// In this case, D subsumes C
// because D is one of
// the cases of C