C++ has always included some simple ways to compute values at compile time. Templates considerably increased the possibilities in this area, and further evolution of the language has only added to this toolbox.
In the simple case, you can decide whether or not to use certain or to choose between different template code. But the compiler even can compute the outcome of control flow at compile time, provided all necessary input is available.
In fact, C++ has multiple features to support compile-time programming:
• Since before C++98, templates have provided the ability to compute at compile time, including using loops and execution path selection. (However, some consider this an “abuse” of template features, e.g., because it requires nonintuitive syntax.)
• With partial specialization we can choose at compile time between different class template implementations depending on specific constraints or requirements.
• With the SFINAE principle, we can allow selection between different function template implementations for different types or different constraints.
• In C++11 and C++14, compile-time computing became increasingly better supported with the constexpr feature using “intuitive” execution path selection and, since C++14, most statement kinds (including for loops, switch statements, etc.).
• C++17 introduced a “compile-time if” to discard statements depending on compile-time conditions or constraints. It works even outside of templates.
This chapter introduces these features with a special focus on the role and context of templates.
Templates are instantiated at compile time (in contrast to dynamic languages, where genericity is handled at run time). It turns out that some of the features of C++ templates can be combined with the instantiation process to produce a sort of primitive recursive “programming language” within the C++ language itself.1 For this reason, templates can be used to “compute a program.” Chapter 23 will cover the whole story and all features, but here is a short example of what is possible.
The following code finds out at compile time whether a given number is a prime number:
basics/isprime.hpp
template<unsigned p, unsigned d> // p: number to check, d: current divisor
struct DoIsPrime {
static constexpr bool value = (p%d != 0) && DoIsPrime<p,d-1>::value;
};
template<unsigned p> // end recursion if divisor is 2
struct DoIsPrime<p,2> {
static constexpr bool value = (p%2 != 0);
};
template<unsigned p> // primary template
struct IsPrime {
// start recursion with divisor from p/2:
static constexpr bool value = DoIsPrime<p,p/2>::value;
};
// special cases (to avoid endless recursion with template instantiation):
template<>
struct IsPrime<0> { static constexpr bool value = false; };
template<>
struct IsPrime<1> { static constexpr bool value = false; };
template<>
struct IsPrime<2> { static constexpr bool value = true; };
template<>
struct IsPrime<3> { static constexpr bool value = true; };
The IsPrime<> template returns in member value whether the passed template parameter p is a prime number. To achieve this, it instantiates DoIsPrime<>, which recursively expands to an expression checking for each divisor d between p/2 and 2 whether the divisor divides p without remainder.
For example, the expression
IsPrime<9>::value
expands to
DoIsPrime<9,4>::value
9%4!=0 && DoIsPrime<9,3>::value
which expands to
9%4!=0 && 9%3!=0 && DoIsPrime<9,2>::value
which expands to
9%4!=0 && 9%3!=0 && 9%2!=0
which evaluates to false, because 9%3 is 0.
As this chain of instantiations demonstrates:
• We use recursive expansions of DoIsPrime<> to iterate over all divisors from p/2 down to 2 to find out whether any of these divisors divide the given integer exactly (i.e., without remainder).
• The partial specialization of DoIsPrime<> for d equal to 2 serves as the criterion to end the recursion.
Note that all this is done at compile time. That is,
IsPrime<9>::value
expands to false at compile time.
The template syntax is arguably clumsy, but code similar to this has been valid since C++98 (and earlier) and has proven useful for quite a few libraries.2
See Chapter 23 for details.
C++11 introduced a new feature, constexpr, that greatly simplifies various forms of compile-time computation. In particular, given proper input, a constexpr function can be evaluated at compile time. While in C++11 constexpr functions were introduced with stringent limitations (e.g., each constexpr function definition was essentially limited to consist of a return statement), most of these restrictions were removed with C++14. Of course, successfully evaluating a constexpr function still requires that all computational steps be possible and valid at compile time: Currently, that excludes things like heap allocation or throwing exceptions.
Our example to test whether a number is a prime number could be implemented as follows in C++11:
basics/isprime11.hpp
constexpr bool
doIsPrime (unsigned p, unsigned d) // p: number to check, d: current divisor
{
return d!=2 ? (p%d!=0) && doIsPrime(p,d-1) // check this and smaller divisors
: (p%2!=0); // end recursion if divisor is 2
}
constexpr bool isPrime (unsigned p)
{
return p < 4 ? !(p<2) // handle special cases
: doIsPrime(p,p/2); // start recursion with divisor from p/2
}
Due to the limitation of having only one statement, we can only use the conditional operator as a selection mechanism, and we still need recursion to iterate over the elements. But the syntax is ordinary C++ function code, making it more accessible than our first version relying on template instantiation.
With C++14, constexpr functions can make use of most control structures available in general C++ code. So, instead of writing unwieldy template code or somewhat arcane one-liners, we can now just use a plain for loop:
basics/isprime14.hpp
constexpr bool isPrime (unsigned int p)
{
for (unsigned int d=2; d<=p/2; ++d) {
if (p % d == 0) {
return false; // found divisor without remainder
}
}
return p > 1; // no divisor without remainder found
}
With both the C++11 and C++14 versions of our constexpr isPrime() implementations, we can simply call
isPrime(9)
to find out whether 9 is a prime number. Note that it can do so at compile time, but it need not necessarily do so. In a context that requires a compile-time value (e.g., an array length or a nontype template argument), the compiler will attempt to evaluate a call to a constexpr function at compile time and issue an error if that is not possible (since a constant must be produced in the end). In other contexts, the compiler may or may not attempt the evaluation at compile time3 but if such an evaluation fails, no error is issued and the call is left as a run-time call instead.
For example:
constexpr bool b1 = isPrime(9); // evaluated at compile time
will compute the value at compile time. The same is true with
const bool b2 = isPrime(9); // evaluated at compile time if in namespace scope
provided b2 is defined globally or in a namespace. At block scope, the compiler can decide whether to compute it at compile or run time.4 This, for example, is also the case here:
bool fiftySevenIsPrime() {
return isPrime(57); // evaluated at compile or running time
}
the compiler may or may not evaluate the call to isPrime at compile time.
On the other hand:
int x;
…
std::cout << isPrime(x); // evaluated at run time
will generate code that computes at run time whether x is a prime number.
An interesting application of a compile-time test such as isPrime() is to use partial specialization to select at compile time between different implementations.
For example, we can choose between different implementations depending on whether a template argument is a prime number:
// primary helper template:
template<int SZ, bool = isPrime(SZ)>
struct Helper;
// implementation if SZ is not a prime number:
template<int SZ>
struct Helper<SZ, false>
{
…
};
// implementation if SZ is a prime number:
template<int SZ>
struct Helper<SZ, true>
{
…
};
template<typename T, std::size_t SZ>
long foo (std::array<T,SZ> const& coll)
{
Helper<SZ> h; // implementation depends on whether array has prime number as size
…
}
Here, depending on whether the size of the std::array<> argument is a prime number, we use two different implementations of class Helper<>. This kind of application of partial specialization is broadly applicable to select among different implementations of a function template depending on properties of the arguments it’s being invoked for.
Above, we used two partial specializations to implement the two possible alternatives. Instead, we can also use the primary template for one of the alternatives (the default) case and partial specializations for any other special case:
// primary helper template (used if no specialization fits):
template<int SZ, bool = isPrime(SZ)>
struct Helper
{
…
};
// special implementation if SZ is a prime number:
template<int SZ>
struct Helper<SZ, true>
{
…
};
Because function templates do not support partial specialization, you have to use other mechanisms to change function implementation based on certain constraints. Our options include the following:
• Use classes with static functions,
• Use std::enable_if, introduced in Section 6.3 on page 98,
• Use the SFINAE feature, which is introduced next, or
• Use the compile-time if feature, available since C++17, which is introduced below in Section 8.5 on page 135.
Chapter 20 discusses techniques for selecting a function implementation based on constraints.
In C++ it is pretty common to overload functions to account for various argument types. When a compiler sees a call to an overloaded function, it must therefore consider each candidate separately, evaluating the arguments of the call and picking the candidate that matches best (see also Appendix C for some details about this process).
In cases where the set of candidates for a call includes function templates, the compiler first has to determine what template arguments should be used for that candidate, then substitute those arguments in the function parameter list and in its return type, and then evaluate how well it matches (just like an ordinary function). However, the substitution process could run into problems: It could produce constructs that make no sense. Rather than deciding that such meaningless substitutions lead to errors, the language rules instead say that candidates with such substitution problems are simply ignored.
We call this principle SFINAE (pronounced like sfee-nay), which stands for “substitution failure is not an error.”
Note that the substitution process described here is distinct from the on-demand instantiation process (see Section 2.2 on page 27): The substitution may be done even for potential instantiations that are not needed (so the compiler can evaluate whether indeed they are unneeded). It is a substitution of the constructs appearing directly in the declaration of the function (but not its body).
Consider the following example:
basics/len1.hpp
// number of elements in a raw array:
template<typename T, unsigned N>
std::size_t len (T(&)[N])
{
return N;
}
// number of elements for a type having size_type:
template<typename T>
typename T::size_type len (T const& t)
{
return t.size();
}
Here, we define two function templates len() taking one generic argument:5
1. The first function template declares the parameter as T(&)[N], which means that the parameter has to be an array of N elements of type T.
2. The second function template declares the parameter simply as T, which places no constraints on the parameter but returns type T::size_type, which requires that the passed argument type has a corresponding member size_type.
When passing a raw array or string literals, only the function template for raw arrays matches:
int a[10];
std::cout << len(a); // OK: only len() for array matches
std::cout << len("tmp"); //OK: only len() for array matches
According to its signature, the second function template also matches when substituting (respectively) int[10] and char const[4] for T, but those substitutions lead to potential errors in the return type T::size_type. The second template is therefore ignored for these calls.
When passing a std::vector<>, only the second function template matches:
std::vector<int> v;
std::cout << len(v); // OK: only len() for a type with size_type matches
When passing a raw pointer, neither of the templates match (without a failure). As a result, the compiler will complain that no matching len() function is found:
int* p;
std::cout << len(p); // ERROR: no matching len() function found
Note that this differs from passing an object of a type having a size_type member, but no size() member function, as is, for example, the case for std::allocator<>:
std::allocator<int> x;
std::cout << len(x); // ERROR: len() function found, but can’t size()
When passing an object of such a type, the compiler finds the second function template as matching function template. So instead of an error that no matching len() function is found, this will result in a compile-time error that calling size() for a std::allocator<int> is invalid. This time, the second function template is not ignored.
Ignoring a candidate when substituting its return type is meaningless can cause the compiler to select another candidate whose parameters are a worse match. For example:
basics/len2.hpp
// number of elements in a raw array:
template<typename T, unsigned N>
std::size_t len (T(&)[N])
{
return N;
}
// number of elements for a type having size_type:
template<typename T>
typename T::size_type len (T const& t)
{
return t.size();
}
// fallback for all other types:
std::size_t len (…)
{
return 0;
}
Here, we also provide a general len() function that always matches but has the worst match (match with ellipsis (…) in overload resolution (see Section C.2 on page 682).
So, for raw arrays and vectors, we have two matches where the specific match is the better match. For pointers, only the fallback matches so that the compiler no longer complains about a missing len() for this call.6 But for the allocator, the second and third function templates match, with the second function template as the better match. So, still, this results in an error that no size() member function can be called:
int a[10];
std::cout << len(a); // OK: len() for array is best match
std::cout << len("tmp"); //OK: len() for array is best match
std::vector<int> v; // OK:
std::cout << len(v);len() for a type with size_type is best match
int* p;
std::cout << len(p); // OK: only fallback len() matches
std::allocator<int> x; // ERROR: 2nd
std::cout << len(x);len() function matches best,
// but can’t call size() for x
See Section 15.7 on page 284 for more details about SFINAE and Section 19.4 on page 416 about some applications of SFINAE.
Over time, the SFINAE principle has become so important and so prevalent among template designers that the abbreviation has become a verb. We say “we SFINAE out a function” if we mean to apply the SFINAE mechanism to ensure that function templates are ignored for certain constraints by instrumenting the template code to result in invalid code for these constraints. And whenever you read in the C++ standard that a function template “shall not participate in overload resolution unless…” it means that SFINAE is used to “SFINAE out” that function template for certain cases.
For example, class std::thread declares a constructor:
namespace std {
class thread {
public:
…
template<typename F, typename… Args>
explicit thread(F&& f, Args&&… args);
…
};
}
with the following remark:
Remarks: This constructor shall not participate in overload resolution if decay_t<F> is the same type as std::thread.
This means that the template constructor is ignored if it is called with a std::thread as first and only argument. The reason is that otherwise a member template like this sometimes might better match than any predefined copy or move constructor (see Section 6.2 on page 95 and Section 16.2.4 on page 333 for details). By SFINAE’ing out the constructor template when called for a thread, we ensure that the predefined copy or move constructor is always used when a thread gets constructed from another thread.7
Applying this technique on a case-by-case basis can be unwieldy. Fortunately, the standard library provides tools to disable templates more easily. The best-known such feature is std::enable_if<>, which was introduced in Section 6.3 on page 98. It allows us to disable a template just by replacing a type with a construct containing the condition to disable it.
As a consequence, the real declaration of std::thread typically is as follows:
namespace std {
class thread {
public:
…
template<typename F, typename… Args,
typename = std::enable_if_t<!std::is_same_v<std::decay_t<F>,
thread>>>
explicit thread(F&& f, Args&&… args);
…
};
}
See Section 20.3 on page 469 for details about how std::enable_if<> is implemented, using partial specialization and SFINAE.
It’s not always easy to find out and formulate the right expression to SFINAE out function templates for certain conditions.
Suppose, for example, that we want to ensure that the function template len() is ignored for arguments of a type that has a size_type member but not a size() member function. Without any form of requirements for a size() member function in the function declaration, the function template is selected and its ultimate instantiation then results in an error:
template<typename T>
typename T::size_type len (T const& t)
{
return t.size();
}
std::allocator<int> x;’; //ERROR:
std::cout << len(x) << ’\nlen() selected, but x has no size()
There is a common pattern or idiom to deal with such a situation:
• Specify the return type with the trailing return type syntax (use auto at the front and -> before the return type at the end).
• Define the return type using decltype and the comma operator.
• Formulate all expressions that must be valid at the beginning of the comma operator (converted to void in case the comma operator is overloaded).
• Define an object of the real return type at the end of the comma operator.
For example:
template<typename T>
auto len (T const& t) -> decltype( (void)(t.size()), T::size_type() )
{
return t.size();
}
Here the return type is given by
decltype( (void)(t.size)(), T::size_type() )
The operand of the decltype construct is a comma-separated list of expressions, so that the last expression T::size_type() yields a value of the desired return type (which decltype uses to convert into the return type). Before the (last) comma, we have the expressions that must be valid, which in this case is just t.size(). The cast of the expression to void is to avoid the possibility of a user-defined comma operator overloaded for the type of the expressions.
Note that the argument of decltype is an unevaluated operand, which means that you, for example, can create “dummy objects” without calling constructors, which is discussed in Section 11.2.3 on page 166.
Partial specialization, SFINAE, and std::enable_if allow us to enable or disable templates as a whole. C++17 additionally introduces a compile-time if statement that allows is to enable or disable specific statements based on compile-time conditions. With the syntax if constexpr(… ), the compiler uses a compile-time expression to decide whether to apply the then part or the else part (if any).
As a first example, consider the variadic function template print() introduced in Section 4.1.1 on page 55. It prints its arguments (of arbitrary types) using recursion. Instead of providing a separate function to end the recursion, the constexpr if feature allows us to decide locally whether to continue the recursion:8
template<typename T, typename… Types>
void print (T const& firstArg, Types const&… args)
{
std::cout << firstArg << ’\n’;
if constexpr(sizeof…(args) > 0) {
print(args…); //code only available if sizeof…(args)>0 (since C++17)
}
}
Here, if print() is called for one argument only, args becomes an empty parameter pack so that sizeof…(args) becomes 0. As a result, the recursive call of print() becomes a discarded statement, for which the code is not instantiated. Thus, a corresponding function is not required to exist and the recursion ends.
The fact that the code is not instantiated means that only the first translation phase (the definition time) is performed, which checks for correct syntax and names that don’t depend on template parameters (see Section 1.1.3 on page 6). For example:
template<typename T>
void foo(T t)
{
if constexpr(std::is_integral_v<T>) {
if (t > 0) {
foo(t-1); // OK
}
}
else {
undeclared(t); // error if not declared and not discarded (i.e. T is not integral)
undeclared(); // error if not declared (even if discarded)
static_assert(false, "no integral"); // always asserts (even if discarded)
static_assert(!std::is_integral_v<T>, "no integral"); //OK
}
}
Note that if constexpr can be used in any function, not only in templates. We only need a compile-time expression that yields a Boolean value. For example:
int main()
{
if constexpr(std::numeric_limits<char>::is_signed {
foo(42); // OK
}
else {
undeclared(42); // error if
undeclared() not declared
static_assert(false, "unsigned"); // always asserts (even if discarded)
static_assert(!std::numeric_limits<char>::is_signed,
"char is unsigned"); //OK
}
}
With this feature, we can, for example, use our isPrime() compile-time function, introduced in Section 8.2 on page 125, to perform additional code if a given size is not a prime number:
template<typename T, std::size_t SZ>
void foo (std::array<T,SZ> const& coll)
{
if constexpr(!isPrime(SZ)) {
… //special additional handling if the passed array has no prime number as size
}
…
}
See Section 14.6 on page 263 for further details.
• Templates provide the ability to compute at compile time (using recursion to iterate and partial specialization or operator ?: for selections).
• With constexpr functions, we can replace most compile-time computations with “ordinary functions” that are callable in compile-time contexts.
• With partial specialization, we can choose between different implementations of class templates based on certain compile-time constraints.
• Templates are used only if needed and substitutions in function template declarations do not result in invalid code. This principle is called SFINAE (substitution failure is not an error).
• SFINAE can be used to provide function templates only for certain types and/or constraints.
• Since C++17, a compile-time if allows us to enable or discard statements according to compile-time conditions (even outside templates).
1 In fact, it was Erwin Unruh who first found it out by presenting a program computing prime numbers at compile time. See Section 23.7 on page 545 for details.
2 Before C++11, it was common to declare the value members as enumerator constants instead of static data members to avoid the need to have an out-of-class definition of the static data member (see Section 23.6 on page 543 for details). For example:
enum { value = (p%d != 0) && DoIsPrime<p,d-1>::value };
3 At the time of writing this book in 2012"fn">4 Theoretically, even with constexpr, the compiler can decide to compute the initial value of b at run time.
5 We don’t name this function size() because we want to avoid a naming conflict with the C++ standard library, which defines a standard function template std::size() since C++17.
6 In practice, such a fallback function would usually provide a more useful default, throw an exception, or contain a static assertion to result in a useful error message.
7 Since the copy constructor for class thread is deleted, this also ensures that copying is forbidden.
8 Although the code reads if constexpr, the feature is called constexpr if, because it is the “constexpr” form of if (and for historical reasons).