Template Metaprogramming is a powerful weapon in the arsenal of C++ developers as it brings several benefits in terms of flexible designs, code optimization and static checks thru early (compile-time) error detection. It is, however, notoriously difficult to grasp (it’s basically a language in itself with its own rules), awkward to read, and incredibly painful to debug.
C++20 Concepts (herein simply “Concepts”) improve the way we do generic programming by introducing new constructs into the language that allow writing better code and avoid resorting to obscure idioms and clumsy trickery. If things such as SFINAE, type traits and metafunctions give you the shivers then Concepts will very likely be much appreciated.
To fully realize the utility of this new feature the programmer needs to be familiar with C++ templates and some traditional metaprogramming techniques used to work around the shortcomings of the language because that’s where the innovation lies. Here we’ll give a quick recap of the fundamentals and mention some of the problems with classic solutions commonly used to solve them.
Introduction
A template, generally speaking, is a parameterized construct from which the compiler generates a family of entities based on the given arguments. In C++ such entities have been traditionally functions and classes, but modern C++ has expanded this set to also include variables, polymorphic lambdas and aliases.
// Function template
template<typename T>
void print(const T& val) {
std::cout << val << std::endl;
}
// Class template
template<typename T>
class pipeline {
public:
void insert(const T& item);
// ...
private:
std::deque<T> queue;
// ...
};
// Variable template
template<typename T>
T price = static_cast<T>(15.30);
// Alias template
template<typename K, typename V>
using cache = std::unordered_map<K, V>;
// Lambda
auto l = [](auto val) { return 0; };
// Generates code similar to the following
struct _lambda_l {
template<typename T>
int operator()(T val) const { return 0; }
};From these templates the C++ compiler generates a family of functions, classes and variables parameterized on the specified types (T,K,V,...). The generation is invoked by using the name of the template with specific type (and also non-type) arguments thru an explicit declaration. For example, the following code would generate specialized versions of the above templates
print<int>(1);
pipeline<object> pline{};
auto whole_price = price<int>;
cache<int, double> lut{};These specialized versions are called template instances and the process of generating them is commonly known as template instantiation. What the compiler does is basically create multiple versions of the template by substituting the template parameters with the arguments specified at the points of usage. Under the hood the compilation would generate the technical equivalent of the following
void print(const int& val) {
std::cout << val << std::endl;
}
class pipeline {
// ...
void insert(const object& item);
// ...
std::deque<object> queue;
};
int whole_price = int(15.30);
std::unordered_map<int, double> lut{};During instantiation the generated code is type-checked to make sure that the template parameters are correctly used within the implementation. Consider, for example, the function template print<T> defined above used as follows (template arguments can be omitted if the compiler can automatically deduce them)
print(std::vector{1, 2, 3});This will not compile and we’ll receive an (usually not very clear) error message that tries to tell us why the instantiation failed. In this case the reason is that the requirements on the template parameter T are not met. Specifically, when T = std::vector the function cannot be instantiated because an STL vector is not “streamable” out of the box – i.e. it does not support stream insertion – so the generated code is incorrect.
Problem #1: Requirements on template parameters
A problem that’s haunted template metaprogramming since its inception is how the requirements on template parameters are enforced by the language. Let’s remember that programming using templates is different from programming using non-templated entities. Template metaprogramming is all about working with implicit interfaces, which are defined by the set of all valid expressions that can be applied to the template parameters.
This decoupling of the algorithms from the data types they can operate upon provides great flexibility as it doesn’t force the programmer to encode the assumptions on the types into explicitly pre-defined interfaces tied to their own implementation. Using the above example, we could rewrite our print<T> template function in non-template form using overloaded standard functions
void print(const int&);
void print(const double&);
void print(const string&);
// ... Add overloads here as neededBy using this approach, the requirements on the types of these concrete interfaces can be easily enforced by the compiler because they are explicitly encoded in the signatures. They are pre-determined contracts that the compiler can immediately check as soon as it sees them. The function only accepts the named types – or anything convertible to them – and nothing else. This check is done at the points of usage without the need for the compiler to see the full definition of the function. If we try to write the following code
print(std::vector{1, 2, 3}); // ERRORwe would promptly receive a concise compilation error describing the fact that there is no matching function for the call to print because it is clearly and explicitly stated that the function does not accept STL vectors.
On the other hand, templates allow for more flexible interfaces that work for all types that meet some requirements without the need to explicitly name what these types are, basically allowing a sort of compile-time duck typing. However, all the flexibility gained by this generic approach comes at the expense of a loose separation between when the assumptions on the template types are checked and when the types are used.
Consider for example the function template print<T> defined earlier but without its definition
template<typename T>
void print(const T& val);We can’t assume much about the types T accepted by such function from just looking at this interface. Typically, these assumptions are laid out in plain natural language as part of the documentation, in the names of the template parameters or, in the worst case, inferred from the function name. For example, in this case we could assume that the type T must be somehow “printable”. Or we could convey such assumptions in the parameter names, as in the following declaration
template<typename Streamable>
void print(const Streamable& val);All of these methods are quite weak as they are merely supported by conventions, best practices, intuition, etc. and the compiler can’t enforce any of them. The problem is that while the requirements on types for concrete interfaces are explicitly expressed in the interfaces themselves, with templates these requirements are implicitly expressed in the implementation of the template. So, relative to the above example, we’d need to check the print<T> algorithm to actually find out that this function only works if the type T is “streamable” (i.e. there is an insertion operator overloaded on T).
There is a very loose separation between assumptions checking and types usage since requirements on parameters can only be enforced by the compiler when the template is instantiated, not at the points of invocation. In the above example where the print<T> function template is being used with a vector argument, the compiler needs to parse the whole definition in order to detect that a vector does not meet the requirements. At that point, we’d expect the compiler to nicely tell us what the problem is when the build fails. Sadly, that’s not the case in many real-world scenarios, as we’ll discuss next.
Problem #2: Diagnostics and debugging
If there is one thing that really drives programmers up the wall is stumbling into an error and getting very little help (or none whatsoever) from the build environment. Unfortunately, compilers have been historically terrible at providing useful, clear and concise error messages when things with templates go awry. To understand the root cause let’s look at what GCC and CLang spit out for the above very simple example of incorrect usage of the print<T> function template.
GCC
---
error: no match for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and 'const std::vector<int, std::allocator<int> >')
... (dozens of error messages follow)
CLang
-----
error: invalid operands to binary expression ('ostream' (aka 'basic_ostream<char>') and 'const std::vector<int>')
... (dozens of error messages follow)The reports are incredibly verbose and if we’re lucky the relevant messages are just at the beginning, like in this case. This issue looks quite simple and in fact it wouldn’t be very difficult for any competent C++ programmer to debug it. But the simplicity of this example is intentional and meant to put the focus on a fundamental problem with error reporting in template metaprogramming.
The problem here is that the reported error is about a specific operation failure on the template argument type, that is operator<< being called with invalid operands, in the template implementation. Since this check is not done at the call site but within the algorithm where the type is used, the information it brings are mixed with other error information in the same context that may be generated if other operations fail as a consequence.
In our example the algorithm is very shallow since it’s just a simple stream insertion, so it’s easy to pinpoint the issue and figure out what’s wrong as all the C++ folks are familiar with this operation. But to better realize the negative effects on the debugging efforts of the programmer let’s consider a variation of our print function with a little more depth defined as follows (full example here)
template<typename T>
void print(const T& val) {
detail::streamer<T> s{};
std::copy(std::begin(val), std::end(val), std::back_inserter(s));
}This function is used to print collection of objects, such as containers, therefore it may be considered a specialization of the original one and might be used as an overload (we’ll see how in the next section). There is still one template parameter but now there are several requirements for it and not all of them are evident by just looking at the definition. We could infer from its use that the value being printed is a container, but that would be only partially correct. In fact, if we call this function as follows
print(std::vector{1, 2, 3}); // OK
print(std::list{"Ciao", "Hello"}); // OK
print(std::map<int, int>{{1, 2}, {3, 4}}); // ERROR
print("123"); // ERRORwe would get compilation errors for several reasons that are not immediately obvious. For example, the compiler would still complain that the call to operator<< is invalid. However, there is no direct use of such operator in the print function so the programmer has to sift thru the error messages to find out that the streamer class is using it, and possibly poke into its implementation to have a better understanding of why it’s so.
Calling it to print an invalid type such as a string literal, even by accident, would generate error messages similar to the following
<source>:15:23: error: type 'int' cannot be used prior to '::' because it has no members
15 | using value_type = C::value_type;
| ^
<source>:26:25: note: in instantiation of template class 'detail::streamer<int>' requested here
26 | detail::streamer<T> s{};
| ^
<source>:34:4: note: in instantiation of function template specialization 'print<int>' requested here
34 | print(123); // ERROR
| ^
<source>:27:15: error: no matching function for call to 'begin'
27 | std::copy(std::begin(val), std::end(val), std::back_inserter(s));
| ^~~~~~~~~~
<source>:34:4: note: in instantiation of function template specialization 'print<int>' requested here
34 | print(123); // ERROR
... (dozens of error messages follow)The compiler complains about unmatched begin and end functions and invalid use of the operator ::. This latter issue would be totally obscure and unrelated to the print interface as it refers to a dependent type on an internal template parameter C (see code) and would probably leave many scratching their heads for a while.
Here, the assumption on the type T is that it must be a “range of streamable values” and we’ll see in the next section one way to define this concept using traditional C++ metaprogramming techniques. A good diagnostic report when trying to invoke the function with a type that does not model this concept should immediately signal this issue at the call site. For example, if called with a std::map we should get terse error messages describing the fact that values of a map are not streamable (not by default). And if invoked with a type that’s not a “range” it should fail right away and tell us just that.
These examples are quite simple but it’s clear how for more complex templates with many nested template invocations this delayed error reporting makes it increasingly difficult to pinpoint the issues. Since template parameters are part of the interface, types that do not meet requirements should be caught at the points of invocation so that any issue can be raised immediately. Going further with the instantiation will pollute the report with all sort of rubbish and ultimately lead to a terrible debugging experience.
Problem #3: Compile-time template function overload
Before delving into a practical example of template overloading, we need to first understand how to express the requirements on template parameters in code. One classic method is to use type traits classes and take advantage of specific template argument substitution rules. So, back again to our print<T> function template, a possible solution to specify the assumptions on the type T is to define an ad-hoc type traits class and use the std::enable_if metafunction from the STL type traits library, like in the following code
// Ad-hoc type trait class for streamable types
template <typename T>
class Streamable
{
template <typename U>
static auto check(U*) -> decltype(std::cout << std::declval<T>());
template <typename>
static void check(...);
public:
static constexpr bool value =
!std::is_void<decltype(check<T>(nullptr))>::value;
};
// Or using the STL type traits library (C++11)
template <typename T, typename = void>
struct Streamable : std::false_type {};
template <typename T>
struct Streamable<T,
std::void_t<decltype(std::cout << std::declval<T>())>
> : std::true_type {};
// Use std::enable_if to enforce the requirements on 'T'
template<typename T, typename = std::enable_if_t<Streamable<T>::value>>
void print(const T& val) {
//...
}There is quite a lot going on in these lines of code and I won’t go into the details here as this topic would deserve an in-depth discussion that would go beyond the scope of this writing. Basically this method requires creating a type traits class (Streamable) in order to extract information from the type T, specifically whether it supports stream insertion. Then it uses the std::enable_if metafunction to enforce the requirement that T must be a “streamable” type. If it is, the template is instantiated. If not, the compilation will fail with an error message indicating that there is no matching function (full example here)
print(1); // OK: ints are streamable by default
print(std::vector{1, 2, 3}); // ERROR: std::vector is not streamableThere are a few quirks in the example, like the use of a non-type std::cout instead of std::ostream which would have made the readability of the code even harder than it already is. But even so we can already feel the awkwardness of this approach, so there is no need to be evil to get the point across.
Consider now a scenario where we want to provide a specialized version of the print template function that works for “ranges”. For our purposes, and for the sake of simplicity, a “range” is simply a collection of elements that can be traversed one after another. The alternative algorithm is the one presented in the previous section, so we have two different implementations as shown in the following code.
// Overload #1
template<typename T>
void print(const T& val) {
std::cout << val << std::endl;
}
// Overload #2
template<typename T>
void print(const T& val) {
detail::streamer<T> s{};
std::copy(std::begin(val), std::end(val), std::back_inserter(s));
}We want to overload on the parameter T so that for ranges the second version is called, and for primitives and other user-defined types the first version is called. So we need to define different requirements on T for the two functions in order to drive the overload resolution. Specifically, the first version should work for all “streamable values that are not ranges” and the second version for all “ranges of streamable values”, which represent the concepts we want to model.
The typical solution to express the requirements for these concepts in modern C++ makes use of the SFINAE rules and type traits classes from the STL type_traits library. By using such techniques we can write the requirements on the template parameter T as follows
// Overload #1
template<typename T,
std::enable_if_t<Streamable_v<T> && !Range_v<T>, bool> = true>
void print(const T& val) {
std::cout << val << std::endl;
}
// Overload #2
template<typename T,
std::enable_if_t<Range_v<T> && Streamable_v<Value_Of_t<T>>, bool> = true>
void print(const T& val) {
detail::streamer<T> s{};
std::copy(std::begin(val), std::end(val), std::back_inserter(s));
}This is a classic C++ metaprorgramming technique to select different algorithms at compile time based on constraints on the template parameters. The Streamable type traits is the same as defined earlier, the only difference being the use of the shorthand form for improved readability (see full example for details). Range is another type traits to check whether T satisfies the requirements of a range (i.e. provides begin/ end methods to define the boundaries), and Value_Of a type traits to check that T is well-formed and provides the actual type of the elements in the range.
template <typename T, typename = void>
struct Streamable : std::false_type {};
template <typename T>
struct Streamable<T,
std::void_t<decltype(std::cout << std::declval<T>())>
> : std::true_type {};
template <typename T, typename = void>
struct Range : std::false_type {};
template <typename T>
struct Range<T,
std::void_t<decltype(std::begin(std::declval<T>())),
decltype(std::end(std::declval<T>()))>
> : std::true_type {};
template <typename T, typename = void>
struct Value_Of {};
template <typename T>
struct Value_Of<T, std::void_t<typename T::value_type>> {
using type = T::value_type;
};The compiler can then check these requirements against the template arguments passed at the call sites and pick the correct overload using the SFINAE rules.
print(123); // calls #1
print("xyz"); // calls #1
print(std::vector{1, 2, 3}); // calls #2
print(std::string{"abc"}); // calls #2
print(std::map<int, int>{{1, 2}, {3, 4}}); // ERROR: std::pair is not streamableNow, while all this just works and is well-established practice in the C++ world, it doesn’t shine for elegance and feels a bit hacky. There is quite a lot of scaffolding code to write for the type traits, and the requirements they enforce are buried in there and not immediately clear. Also, the examples presented here are quite trivial. For more complex cases with multiple template parameters and relationships between them, modelling the assumptions using these techniques will quickly turn the code into a mud ball.
Conclusions
We’ve seen what defining requirements on template parameters means, the C++ limitations on the ability to enforce them, and the implications on code readability, debugging experience and template overloading. Classic solutions that are pretty common in C++ template metaprogramming require writing verbose and obscure code that has a lot of the workaround feeling typical of many C++ idioms.
Modern metaprogramming requires a better experience for sure (unless you’re a C++ template fundamentalist of course). In the next article we’ll see how C++ Concepts eliminate the need for all this boiler-plate code and ad-hoc solutions by providing native language constructs that allow writing cleaner and more expressive templates.