Templates Notes

Page Contents

Variadic Templates

The template parameter pack (T...) allows a template to accept a variable number of type parameters.

The function parameter pack (Args...): allows functions to accept a variable number of arguments of any type.

The parameter pack expansion (args...): unpacks a parameter pack into separate arguments.

Get The Number Of Arguments In A Parameter Pack

To get the number of arguments in a parameter pack use the sizeof... operator like, which is evaluated at compile time, as follows:

template <typename T, typename... Args>
void someFunction(T, a, Args... args) {
    std::cout << "There are " << sizeof...(Args) << " arguments\n";
    std::cout << "There are " << sizeof...(args) << " arguments\n"; // Will return same as for Args
}

Parameter Pack vs Expansion

  • sizeof...(args) returns the size of the pack
  • sizeof(args)... expands the parameter pack and applies sizeof() to each expanded item.

The expansion example applies to any function. We could write MyFunc(args)..., for example, which would expand the pack and apply MyFunc to each item.

Variadic Function Templates

Use function overloading to define a base case and the recuring case:

// This is the base case
template <typename T>
T myFunction(T lhs, T rhs) {
    return lhs * rhs; // ... Any operation that does something with p1 and p2
}

// This is the recursive case
template <typename T, typename... Args>
T myFunction(T lhs, Args... rhs) {
    return myFunction(lhs, myFunction(rhs...));
}

int main() {
    printf("%u\n", myFunction(1U, 2U, 3U, 4U));
    return 0;
}

We can use CPPInsights.io to see that this generates the following template instantiations:

unsigned int myFunction<unsigned int, unsigned int, unsigned int, unsigned int>(
        unsigned int lhs, unsigned int __rhs1, unsigned int __rhs2, unsigned int __rhs3)
{
  return myFunction(lhs, myFunction(__rhs1, __rhs2, __rhs3));
}

template<>
unsigned int myFunction<unsigned int, unsigned int, unsigned int>(
        unsigned int lhs, unsigned int __rhs1, unsigned int __rhs2)
{
  return myFunction(lhs, myFunction(__rhs1, __rhs2));
}

template<>
unsigned int myFunction<unsigned int>(
    unsigned int lhs, unsigned int rhs)
{
  return lhs * rhs;
}

Which would then get inlined by the compiler, and further more for such a simple example, even on O1 optimisation level, the result is computed at compile time. We can observe this using the GodBolt compiler explorer, which outputs the following ARM asm:

.LC0:
        .ascii  "%u\012\000"
main:
        push    {r3, lr}
        movs    r1, #24
        movw    r0, #:lower16:.LC0
        movt    r0, #:upper16:.LC0
        bl      printf
        movs    r0, #0
        pop     {r3, pc}

As we can see, the are no function calls to myFunction, just the result!

Fold Expressions

A fold expression allows you to apply an operator to a parameter pack in a concise way and is a nice way of simplifying recursive template logic...

template<typename T>
T sum(T a) {
    return a;
}

template <typename T, typename... Args>
T sum(T a, Args... args) {
    return a + sum(args...);
}

Becomes just this:

template <typename... T>
int sum(T... args) {
    return (... + args);
}

Using CPPInsights.io, we can see that this would produce:

template<typename ... T>
int sum(T... args)
{
  return (... + args);
}

// This is generated by the compiler for us...
template<>
int sum<unsigned int, unsigned int, unsigned int, unsigned int>(unsigned int __args0, unsigned int __args1, unsigned int __args2, unsigned int __args3)
{
  return static_cast<int>(((__args0 + __args1) + __args2) + __args3);
}

int main()
{
  sum(1U, 2U, 3U, 4U);
  return 0;
}

In general you can have these:

  • (args op ... [op init]):
    • E.g. (args + ...) expands to (args[0] + (args[1] + (... + (args[N-1] + args[N]))))
    • E.g. (args + ... + 99) expands to (args[0] + (args[1] + (... + (args[N-1] + (args[N] + 99)))))
  • ([op init] ... op args)
    • E.g. (... + args) expands to ((((args[0] + args[1]) + args[2]) + ...) + args[N])
    • E.g. (99 + ... + args) expands to (((((99 + args[0]) + args[1]) + args[2]) + ...) + args[N])

The parameter pack can also be part of an expression. E.g.: (somefunc(args), ...).

Variadic Class Templates

Same as for functions but rather than overloading a function name, template specialisation is used:

Perfect Forwarding

This was a really good and detailed watch regarding perfect forwarding and universal/forwarding references.

Good Vids Etc

Credits

The follow section is very heavily based on "Template Metaprogramming with C++" by Marious Bancila. I just changed some of the examples to encuorage my brain to mull it over more thoroughly and have tried to explain things to myself in more detaill (read bigger pictures smaller words).

Type Traits

Two kinds:

  1. The first kind of type trait is a small class template that contains a constant value, where the value represents the answer to a question we ask about a type.

For example:

#include <iostream>

class MyClass {
};

template <typename T>
struct is_my_class
{
    static constexpr bool value = false;
};


template <>
struct is_my_class<MyClass>
{
    static constexpr bool value = true;
};

template <typename T>
inline constexpr bool is_my_class_v = is_my_class<T>::value;

int main() {  
    std::cout << "Int is MyClass? " << is_my_class_v<int> << "\n";
    //                                 ^^ Shorthand for `is_my_class<int>::value`

    std::cout << "MyClass is MyClass? " << is_my_class_v<MyClass> << "\n";
    //                                     ^^ shorthad for `is_my_class<MyClass>::value`

    return 1;
}

///
/// Outputs:
/// Int is MyClass? 0
/// MyClass is MyClass? 1
[Run code here]

  1. The second kind enables type transformation at compile time. E.g. adding or removing const qualifier, or pointer/reference from a type. These are metafunctions.

Substitution Failure Is Not An Error (SFINAE)

Used to restrict template types. For example creating a function template that only works with certain types.

SFINAE is now "old". The new kid on the block is C++20 concepts. This sections discusses SFINAE, however.

SFINAE means that when the compiler substitures arguments into a template (instanitation), if the substituation is invalid, it does not result in an error, just a deduction failure. It is only an error if no deduction succeeds, but if even one does, there is no error.

E.g.

#include <iostream>

template <typename T>
auto begin(T &c) { return c.begin(); }

template <typename T, size_t N>
T* begin(T (&arr)[N]) { return arr; }

If we do the following:

int myArray[] {1,2,3,4};
int *iter = begin(myArray);

The compile first tries to subsitute int [4] into the fist template. This fails. But there is no error because of SFINAE. It is just treated as a deduction failure and the compiler moves on to trying to instantiate int[4] into the second template, which works, so it is chosen and create the following instantiation:

template<>
int* begin<int, 4>(int (&arr)[4])
{
  return arr;
}

So, to recap, rather than causing a hard error, this first candidate was removed from consideration. This is a key part of the SFINAE (Substitution Failure Is Not An Error) rule:

  1. The compiler considers all viable template candidates.
  2. It attempts to substitute the provided arguments into each template.
  3. If substitution fails for a candidate, that candidate is removed from consideration (instead of causing a hard error).
  4. The most specific remaining candidate is selected. If there is ambiguity or no valid candidate, compilation fails.

Not SFINAE But Sets The Ground Work For How Its Useful

Contrived, but anyway... There is bank A and bank B, both of which support SWIFT transfers. We cannot modify their API.

class BankA_Account {
public:
    // ...
    int transfer(double amount, SWIFT &destination) {
        // ...
        return 0;
    }
};

class BankB_Account {
public:
    // ...
    bool sendMoney(double amount, SWIFT &destination) {
        // ...
        return true;
    }
};

I want to be able to have a generic function bool transfer(??? BankAccount, double amount, SWIFT &destination) that can accept a bank A or bank B account.

As neither Bank A nor bank B inherit from a common ancestor runtime polymorphism is not possible. We could write wrapper classes that derive from a common base, and this might be a good way of doing it. Some downsides might be incurring the cost of the VTable lookups, having to write a wrapper for every bank API provider, etc. But, not considering that here... its just a contrived example to show some SFINAE... not saying this is how the problem should be solved.

So, continuing, the solution might be templates. Lets try:

template <typename T>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.transfer(amount, destination) != -1;
}

template <typename T>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.sendMoney(amount, destination);
}

Nope. The compiler, unsuprisingly, gives us the following warning:

main.cpp:31:6: error: redefinition of 'transfer'
bool transfer(T& account, double amount, SWIFT &destination) {
     ^
main.cpp:26:6: note: previous definition is here
bool transfer(T& account, double amount, SWIFT &destination) {

[See full example here]

So what can be done?! Template trickery to make sure the compiler only "sees" on of the definitions of transfer is the answer :o

First of all a type trait: 

template <typename T>
struct bank_account_uses_transfer_method {
    static constexpr bool value = false;
};

template <>
struct bank_account_uses_transfer_method<BankA_Account> {
    static constexpr bool value = true;
}

template <typename T>
inline constexpr bool bank_account_uses_transfer_method_v = bank_account_uses_transfer_method<T>::value;

Now we can determine at compile time whether a bank account has the transfer function.

Next we need to stop one of the transfer definitions from being considered at all. Do this by adding a boolean switch as a non-type template parameter: 

template <typename T, bool uses_transfer>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.sendMoney(amount, destination) != -1;
}

template <typename T, true>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.transfer(amount, destination);
}

Nope, we get this error:

error: function template partial specialization is not allowed
bool transfer<true>(T& account, double amount, SWIFT &destination) {
     ^       ~~~~~~
1 error generated.

In C++ function template partial specialisation is not allowed. The way round this is to wrap the functions in a class.

template <bool> // Anonymous non-type parameter - not used in impl
struct transfer_wrapper {
    template <typename T>
    static bool transfer(T& account, double amount, SWIFT &destination) {
        return account.sendMoney(amount, destination) != -1;
    }
};

template<>
struct transfer_wrapper<true> {
    template <typename T>
    static bool transfer(T& account, double amount, SWIFT &destination) {
        return account.transfer(amount, destination);
    }
};

Now, is we have an object of either bank type we can do:

transfer_wrapper<bank_account_uses_transfer_method_v<MY_BANK_OBJ>>::template transfer<MY_BANK_OBJ>(account, amount, destination);

As a side note, why did we need to use the template keyword in ...template transfer<MY_BANK_OBJ>(... above? Without template, the compiler assumes transfer could be a normal static member (not a template) and the keyword disamiguates this.

We can tidy this up using another template function...

template <typename T>
static bool transfer(T& account, double amount, SWIFT &destination) {
    return transfer_wrapper<bank_account_uses_transfer_method_v<T>>::template transfer<T>(account, amount, destination);
}

Which, in turn, can be further tidied because transfer()'s T can be inferred:

template <typename T>
static bool transfer(T& account, double amount, SWIFT &destination) {
    return transfer_wrapper<bank_account_uses_transfer_method_v<T>>::template(account, amount, destination);
}

The whole thing becomes:

#include <iostream>

class SWIFT {
};

class BankA_Account {
public:
    // ...
    int transfer(double amount, SWIFT &destination) {
        // ...
        std::cout<< "Bank A transfer " << amount << "\n";
        return 0;
    }
};

class BankB_Account {
public:
    // ...
    bool sendMoney(double amount, SWIFT &destination) {
        // ...
        std::cout<< "Bank B transfer " << amount << "\n";
        return true;
    }
};

template <typename T>
struct bank_account_uses_transfer_method {
    static constexpr bool value = false;
};

template <>
struct bank_account_uses_transfer_method<BankA_Account> {
    static constexpr bool value = true;
};

template <typename T>
inline constexpr bool bank_account_uses_transfer_method_v = bank_account_uses_transfer_method<T>::value;

template <bool> // Anonymous non-type parameter - not used in impl
struct transfer_wrapper {
    template <typename T>
    static bool transfer(T& account, double amount, SWIFT &destination) {
        return account.sendMoney(amount, destination) != -1;
    }
};

template<>
struct transfer_wrapper<true> {
    template <typename T>
    static bool transfer(T& account, double amount, SWIFT &destination) {
        return account.transfer(amount, destination);
    }
};

template <typename T>
static bool transfer(T& account, double amount, SWIFT &destination) {
    return transfer_wrapper<bank_account_uses_transfer_method_v<T>>::transfer(account, amount, destination);
}

int main() {
    SWIFT s;
    BankA_Account a;
    BankB_Account b;

    transfer(a, 11, s);
    transfer(b, 321, s);

    return 0;
}

// Outputs:
// Bank A transfer 11
// Bank B transfer 321
[See full example here]

Note, that SFINAE has not yet been used. In the above example there were no substitution failures. The following is an example of the type deduction suceeding:

template <bool> 
struct transfer_wrapper {
    template <typename T> // [T == BankA_Account]
    static bool transfer(T /*[BankA_Account]*/ & account, double amount, SWIFT &destination) {
        return account.sendMoney(amount, destination) != -1; //< This does **NOT** cause a deduction failure because SFINAE only applies
                                                             //  to template params, function return type and params.
    }
};

Had the above deduction been chosen, it would have resulted in a compile time error: the compiler would have complained that the type BankA_Account does not have a member function sendMoney()! The reason the compile time error did not arise is that this candidate would not be chosen (and therefore realised), because the more specialised template would have been chosen. Thus, SFINAE is not in use here. Just the normal template deduction and selection process.

And breath... There is a lot of complexity here and its quite hard to read. Next we see how enabling SFINAE help reduce this complexity and makes things easier to read.

Making The Previous Example Neater Using SFINAE (Using enable_if)

The type trait enable_if is a metafunction. It will help do what we did above but this time by enabling SFINAE to remove candatates from a function's overload set.

A possible implementation is this:

template<bool B, class T = void>
struct enable_if {};

template<class T>
struct enable_if<true, T> { typedef T type; };

Remember earlier, when we wanted to write the following, but couldn't because functions templates cannot be partially specialised?

template <typename T, bool uses_transfer>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.sendMoney(amount, destination) != -1;
}

template <typename T, true>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.transfer(amount, destination);
}

Well, now, with a little fiddle, we can!

template <typename T, 
          typename std::enable_if<!bank_account_uses_transfer_method_v<T>>::type* = nullptr
>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.sendMoney(amount, destination) != -1;
}

template <typename T,
          typename std::enable_if<bank_account_uses_transfer_method_v<T>>::type* = nullptr
>
bool transfer(T& account, double amount, SWIFT &destination) {
    return account.transfer(amount, destination) != -1;
}

And this is all we need. We don't need the wrapping structures or the generic function that hides the use of the structs etc. It also reads more easily. Each function is only enabled if the condition bank_account_uses_transfer_method_v is met or not.

How does it work? In the example before, we saw that the body of the function wasn't used during the deduction process, so previously, when the compiler tried to substitute BankA_Account into the template that used T.sendMoney, this would not influence the deduction, hence the trick with the wrapper class. However, using enable_if we have now forced that substitution to happen in the template parameter list, and hence it will take part in the deduction!

Lets be the compiler and choose T as BankA_Account. The first of the template functions above becomes:

template <BankA_Account, 
          typename std::enable_if<!bank_account_uses_transfer_method_v<BankA_Account>>::type* = nullptr
>
bool transfer(BankA_Account& account, double amount, SWIFT &destination) { ...account.sendMoney... }

Because bank_account_uses_transfer_method_v<BankA_Account> is true we get:

template <BankA_Account, 
          typename std::enable_if<false>::type* = nullptr
>
bool transfer(BankA_Account& account, double amount, SWIFT &destination) { ...account.sendMoney... }

Expanding further:

template <BankA_Account, 
          typename struct {}::type* = nullptr
>
bool transfer(BankA_Account& account, double amount, SWIFT &destination) { ...account.sendMoney... }

Oops substitution failure! struct {} has no static member type. Substitution fails, removing this function overload from the set of viable candidates.

What happens with the other function, when T is BankA_Account?

template <BankA_Account,
          typename std::enable_if<bank_account_uses_transfer_method_v<BankA_Account>>::type* = nullptr
>
bool transfer(T& account, double amount, SWIFT &destination) { ...account.transfer... }

This becomes:

template <BankA_Account,
          typename std::enable_if<true>::type* = nullptr
>
bool transfer(T& account, double amount, SWIFT &destination) { ...account.transfer... }

And then:

template <BankA_Account,
          struct { typedef BankA_Account type; }::type* = nullptr
>
bool transfer(T& account, double amount, SWIFT &destination) { ...account.transfer... }

Which is:

template <BankA_Account,
          BankA_Account* = nullptr
>
bool transfer(T& account, double amount, SWIFT &destination) { ...account.transfer... }

Which works! The type is successfully deduces as BankA_Account.

This enable_if has allowed us to select a function instatiation at compile time!

Compile Time If: if constexpr

The following is taken from n3329, where static if was proposed, and eventually became if constexpr. I've changed it to use if constexpr, removed a check on the iterators for simplicity and changed has_trivial_copy_constructor to is_trivially_constructible.

template <class It, class T>
void uninitialized_fill(It b, It e, const T& x) {
    if constexpr (std::is_trivially_constructible<T>::value) {
        // Doesn't matter that the values were uninitialized
        std::fill(b, e, x);
    } else {
        // Conservative implementation
        for (; b != e; ++b) {
            new(&*b) T(x);
        }
    }
}

How would this be implemented if the compile time conditional didn't exist?

#include <iostream>
#include <type_traits>

template <class It, class T>
void uninitialized_fill(
            It b,
            It e,
            const T &x,
            const typename std::enable_if<
                std::is_trivially_constructible<T>::value,
                T>::type* p = nullptr
) {
    // Doesn't matter that the values were uninitialized
    std::fill(b, e, x);
}

template <class It, class T>
void uninitialized_fill(
        It b,
        It e,
        const T& x,
        const typename std::enable_if<
            !std::is_trivially_constructible<T>::value,
            T>::type* p = nullptr
) {
    // Conservative implementation
    for (; b != e; ++b) {
        new(&*b) T(x);
    }
}

So, already its harder to grok! Using constexpr if has reduce the amount of code and the cognitive burden required to understand the code. Happy days.

By the way, the following is not compilable, as one might expect (I did and learnt otherwise lol):

template <class It, class T>
void uninitialized_fill(
            It b,
            It e,
            const typename std::enable_if<
                std::is_trivially_constructible<T>::value,
                T>::type& x
) {
    // Doesn't matter that the values were uninitialized
    std::fill(b, e, x);
}

The reason is that deduction only works for directly used template parameters: when a template parameter appears inside another template (like std::enable_if<>), it is not considered for deduction. Stack overflow to the rescue with a detailed explaination.