Using C++ templates

The template engine is one of the fun things about C++. They are a useful tool that helps you cut down on duplicating boiler plate code in generic situations, but they can be used for some other cool things. Here are some examples.

Type checking example

You want a function that returns the the maximum of two numbers, and you want it to do a little bit of type checking to make sure you are comparing the same type of numbers. Then you can write a template function like

template <typename T>
constexpr const T& max(const T& a, const T& b)
{
    return lhs < rhs ? rhs : lhs;
}

If you tried to pass varaibles of different types, e.g., int and long, then the compiler would throw an error since it does the check at compile time.

Parameter packing / loop unpacking

Recall that in C, if you wanted to pass a variable number of parameters to a function, you would need to make use of the va_arg macro. For example,

int sum(int nargs, ...)
{
  int result = 0;
  va_list params;
  va_start(params, nargs);
  for(int i=0; i<nargs; ++i)
  {
    result += va_arg(params, int);
  }
  va_end(params);
  return result;
}

Then calling sum(3, 1, 2, 3) would return 6. The drawback to this is that C does not do any type checking, and this can lead to undefined behaviour or exploits if the programmer is not careful.

C++11 introduces variadic templates. It is basically a template with a variable number of parameters. Since the template engine can do type checking, it is a safer way to write variable argument functions. Here is the parameter packed equivalent:

// Base case
int sum() { return 0; }

// Recursion
template<typename T, typename... Targs>
T sum(T first, Targs... rest)
{
  return first + sum(rest...);
}

or with fold expressions in C++17

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

Perfect forwarding

C++ has the concepts of lvalue and rvalue. Roughly speaking, lvalues are objects or functions, and rvalues are temporary objects or constants (see n3055). When you are passing function arguments into other functions, in a lot of situations you ideally want to preserve the type, for example, to prevent the creation of extra unnecessary temporary objects. This is the forwarding problem (see N1385).

For example:

int ding(int& a)
{
  return dong(a);
}

int dong(int a)
{
  ...
}

would create a temporary variable when passing into dong(). If you wanted to handle all the different situations you could overload that function with all the different forms. However, a better way is to use the forwarding mechanism. If you define

template<class T>
int ding(T&& arg) 
{
  // forwards as original lvalue or rvalue type
  return dong(std::forward<T>(arg));
}

then the template engine will determine the type to forward accordingly.

Curiously Recurring Template Pattern (CRTP)

In object oriented programming, people often define classes that inherit properties of other classes.

class Base
{
public:
...
};

class Derived: public Base
{
public:
...
};

In this example, it’s possible to cast objects of type Derived to Base type at runtime and use it like a Base object. This is the idea of polymorphism. When this happens, the program needs to look up pointers in the virtual table to find the correct underlying objects to point to. These pointer indirections (dynamic dispatch) can lead to small performance hits. Often, this is not necessary in practice, and we are really only interested in using inheritence as a mechanism to enforce interfaces.

An alternative approach is static dispatch, where the redirection is wired up at compile time, and no pointer hopping occurs. You lose the ability to do polymorphism, but trade it for small performance improvements. This can be done using the Curiously Recurring Template Pattern (CRTP), which uses the template engine to hardwire the correct type at compile time.

template<typename T>
class Base
{
public:
  void standard_function()
  {
    static_cast<T*>(this)->std_fn_impl();
  }
};

class Derived : Base<Derived>
{
public:
  void std_fn_impl();
};

Traits and Concepts

Template arguments are very generic and can take on any type. While this makes creating generic code nice, often we want the compiler to do some kind of type checking to help catch bugs. The C++ STL introduced type traits since C++11. These are a bunch of template specialisations that allow you to ask questions about type and do transformations, at compile time. You could for example enforce argument types in template functions

template <typename T>
T function(T x)
{
    static_assert(std::is_integral<T>::value, "Integral values needed.");
    return x;
}

or have conditional compilation of template code (enable_if). Under the hood, it is just a bunch of specialised definitions for each type, like

template<>
struct is_integral<int>
{
  static bool value = true;
}

Concepts in C++20 takes this further, and introduces compiler validation of template arguments by making restrictions part of the templating system (wiki).

For example, to constrain the input to a hashable value,

template<Hashable T>
void lookup(Dict some_dict, T key) {
  ...
}

Metaprogramming

We have seen examples of metaprogramming already, where the template engine is used to compute type deductions, and what not. It turns out you can also use the template engine to compute things you would otherwise do in runtime. Many people even suspect the template engine could be Turing complete. Since all the heavy lifting is done at compile time, people realised there were performance gains to be had! Sadly, your $O(n!)$ algorithm is still going to take $O(n!)$ of computation by the template engine, and since it often requires a recursive style of programming, you are may run into memory issues during compilation (you can increase this limit). But if none of those are problems for you, you can take advantage of sweet, sweet, $O(1)$ lookups to precomputed solutions at runtime.

A toy example is to compute the Fibonacci numbers,

template<int n>
struct Fib
{
  static const int value = Fib<n-1>::value + Fib<n-2>::value;
};

template<>
struct Fib<0>
{
  static const int value = 0;
};

template<>
struct Fib<1>
{
  static const int value = 1;
};

or

constexpr int Fib(const int n) 
{
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  return Fib(n-1) + Fib(n-2);
}

With such versatility, it’s easy and often fun to get carried away, and go down a rabbit hole of templating. Templates are also notorious for producing unreadable walls of error messages if there are issues, even producing competition worthy walls of text. Templates can also be intimidating and present redability challenges, so it’s best to use them judiciously. But at the end of the day, templates solve a bunch of common problems, and every C++ programmer should add them to their toolkit.

– Banner photo by Florian Krumm on Unsplash