Template metaprogramming is one of the most powerful features of C++. It gives your code readability, re usability and flexibility. One of the core concepts of template metaprogramming is SFINAE - Substitution Failure Is Not An Error. In this post, I will describe in brief what is SFINAE, where can you use it and some modern C++ features that can help with template metaprogramming.
What is SFINAE
Consider this definition of the function foo
template<typename T>
void foo(const T& t) {
std::cout << t.value << std::endl;
}Pretty standard template declaration. foo takes an argument of some type T and prints the value of the field named value. Of course, T must be a type that has the value field. For example
struct Bar {
int value = 2;
};
int main() {
foo(Bar());
return 0;
}prints 2. Because the type Bar has a field called value, this type "matches" the type expected by foo and our life is happy. We can think of it as if the compiler is substituting Bar in place of T and when it sees it falls perfectly in place, it gives us a green signal.
What happens if we do this?
struct Baz {
int notvalue = 2;
};
int main() {
foo(Baz());
return 0;
}It gives an error saying -
error: ‘const struct Baz’ has no member named ‘value’; did you mean ‘notvalue’?which is expected, since it does not actually have a member named value. When the compiler goes to substitute Baz in place of T it sees that it does not fit because it's missing the value member.
We can make this work by providing another overload for foo -
void foo(const Baz& baz) {
std::cout << baz.notvalue << std::endl;
}Now this is another "version" of foo that accepts a Baz and prints the notvalue member.
But what happened here? Previously the compiler was upset because it couldn't substitute Baz in place of T. We have added a new overload which accepts Baz but the old template is still there. When the compiler is looking for which overload of foo can be called with a Baz parameter, it tries to substitute Baz in place of T in the first template, and fails. Then it moves down and finds the specialised version of foo and becomes happy.
But why didn't we get an error this time since the substitution failed this time also? Not even a single warning?
Say hello to SFINAE - Substitution Failure Is Not An Error. In order to understand this let's take a look at a simplified picture of what happened during compilation of the program.
- When the compiler saw the line
foo(Baz())it performed a name lookup. In other words it searched for the namefooand found out the two candidates - our templated function and the specialised function. These two are our viable candidates. - Then it moved to the templated
fooand deduced the type ofTfrom the actual parameters passed to the function, in this caseBaz. It then replaced all occurrences ofTin the function parameters and return type withBaz. So the code looks like this -
void foo(const Baz& t) {
std::cout << t.value << std::endl;
}Now at this point, we get an invalid code and the substitution fails. This is where SFINAE comes in. Instead of raising an error, the compiler simply removes it from the set of viable functions.
3. In this case, we do have another viable candidate - the version of foo that accepts a Baz and this works! So we have found a match and the program compiles.
So, in layman terms, the compiler performs the following steps -
- Name lookup and construct the set of viable candidates.
- For function templates, deduce the type of the template parameter from the actual parameters passed to the function.
- Substitute the actual type in place of the template parameter.
- If this leads to invalid code, remove this overload from the set of viable candidates. This is the point of SFINAE.
- At the end we have a set of functions that work with the type provided. If this set is empty, we get a compilation error (like what happened in the first program). If we have more than one function that matches, we have an ambiguity. In this case, we pick the one that matches the closest.
Let's take a look where we can have more than one matches -
struct Bar {
int value = 2;
};
struct Baz {
int notvalue = 2;
};
struct Wut: Baz {
int val = 3;
};
template<typename T>
void foo(const T& t) {
std::cout << t.value << std::endl;
}
void foo(const Baz& baz) {
std::cout << baz.notvalue << std::endl;
}
void foo(const Wut& wut) {
std::cout << wut.val << std::endl;
}
int main() {
foo(Wut());
return 0;
}Here we have added a class Wut that inherits from Baz and another overload for foo that accepts a Wut.
In this case, we have two matches for foo(Wut()). Since Wut inherits from Baz, it can be used where a Baz is expected, so that foo(const Baz&) works with Wut and obviously foo(const Wut& wut) also works.
In this case we choose the 3rd overload, because it's the best match. Hey, it accepts exactly what we're trying to shove down its throat!
Now that we know what SFINAE is, let's write some code that use SFINAE to do cool stuff, and some code which provide some alternative to SFINAE.
For our first program, we want to write a template that "activates" only for integral types (these are bool, char, char8_t , char16_t, char32_t, wchar_t, short, int, 'long, long long or any implementation-defined extended integer types, including any signed, unsigned, and cv-qualified variants.)
We need to have a way to check if a type is integral or not. Fortunately, C++ provides a way. In the header <type_traits>, we have an utility std::is_integral<T> which is a struct who has a value member which is true if T is integral or is false otherwise
#include<type_traits>
#include<iostream>
int main() {
std::cout << std::boolalpha; // So that booleans are printed as true or false instead of 1 and 0
std::cout << std::is_integral<float>::value << '\n'; // false
std::cout << std::is_integral<int>::value << '\n'; // true
std::cout << std::is_integral<bool>::value << '\n'; // true
}Now we want to write a function foo that will accept only integral types. For that we would like to write a helper template that gets activate whenever some condition is true. Let's call it enable_if (wink, wink)
We want enable_if<condition, T> to become invalid when condition is false. When condition is true though, we need to access T. So let's make enable_if a struct which has a member called type that produces T
template<bool B, typename T>
struct enable_if {
typedef T type;
}Now when we do enable_if<condition, T>::type we get back T. But so far we have not used the condition. We need to use SFINAE. So the obvious way is to make it so that enable_if<condition, T> does not have the type member when condition is false. Then enable_if<condition, T>::type will trigger SFINAE.
template<bool B, typename T>
struct enable_if {};
template<typename T>
struct enable_if<true, T> { typedef T type; };Now we can use this enable_if to write a function that works for integral types only.
template<typename T>
typename enable_if<std::is_integral<T>::value, T>::type
foo(T t) {
std::cout << "T is integral" << std::endl;
return t;
}And we call it with any integral type and it works. Pass it anything other than integral type and it fails.
foo(1); // Works
foo("A"); // ErrorNote that we used enable_if in the return type of the function. We could have used it in the parameters list also -
template<typename T>
void f(typename enable_if<std::is_integral<T>::value, T>::type t) {
std::cout << "T is integral" << std::endl;
}But in that case foo(1) won't work. Because the compiler won't be able to deduce T from the parameter, and we need to explicitly mention what is T
foo(1); // Doesn't work, template argument deduction/substitution failed, couldn't deduce template parameter ‘T’
foo<int>(1); // Works.Turns out this construct is so useful that since C++11, we have by default enable_if defined in the header <type_traits> and it's used the exact same way.
Since C++14, we have a shorthand for enable_if<...>::type and since C++17, we have shorthand for is_integral<T>::value. So, if you are using C++17, you can write is_integral_v<T> as a shorthand for is_integral<T>::value and enable_if_t<..> as a shorthand for enable_if<..>::type
template<typename T>
typename std::enable_if_t<std::is_integral_v<T>, T>
foo(T t) {
std::cout << "T is integral" << std::endl;
}Now let's look at another interesting problem, and try to implement it with SFINAE, and then look at few modern C++ features that can be used in place of SFINAE to make it concise and expressive rather than a weird trick.
We want to write a template like is_integral but rather than saying if the type is integral or not, it would tell us it the type has a member function named foo or not. For example -
struct A {
std::string foo() {
return "foo() from A";
}
};
struct B {
int foo = 2;
};
struct C {};
int main() {
std::cout << std::boolalpha
std::cout << HasFoo<A>::value; // Should be true
std::cout << HasFoo<B>::value; // Should be false, foo is not a function
std::cout << HasFoo<C>::value; // Should be false
}Before we go to the solution, let us play with templates a bit more. Can you guess which overload for foo will be chosen here?
template<typename T>
void foo(T t) { t.oops(); }
void foo(int t) { std::cout << "foo(int)" << std::endl; }
foo(1);If you guessed the specialised foo, you're absolutely right. The 2nd foo is a better match for int.
What about now?
template<typename T>
void foo(T t) { t.oops(); }
void foo(...) { std::cout << "foo(...)" << std::endl; }
foo(1);Now our 2nd foo is a variadic function, which is just a black hole that accepts anything. You might think, since t.oops() is not valid for int, the templated foo will trigger SFINAE and the variadic version will be chosen. Well, no! Remember, template type substitution occurs in function parameters list and return type, not in the body of a function. Variadic functions are lower in priority than templates and since there is no problem in substituting int for T in the parameters list and return type, the compiler happily chooses templated foo but gets really upset when it sees t.oops() later.
The moral of the story is, if we can somehow get SFINAE to reject a type that does not have foo defined, we can use a black hole to accept it. So that we have more or less this structure for our template HasFoo
template<typename T>
struct HasFoo {
template<typename ???>
static ??? test(???) { } // Accepts only types which have foo defined
static ??? test(...) { } // The black hole.
static const bool value = ???
};The members are static because we want to use them without creating object.
Alright, now we want to do SFINAE on the test function so that it rejects if foo is not defined in T. One solution that comes to mind is something like this -
template<typename T>
typename T::foo test(T t) { return t.foo; }Unfortunately it checks if foo is a member variable and not a member function. Indeed this will work for B but fail for A. We really need some way to tell the compiler that foo should be a function. How do we do that?
Here we use another trick. We know that a template can also accept non type parameters, as we have seen in enable_if
template<typename T>
struct enable_if<true, T> ...Here enable_if accepts a true parameter. Almost like function. Well, you can't pass anything you want like a function. In fact, these are the only things you can use (from the wiki) -
- lvalue reference type (to object or to function);
- an integral type;
- a pointer type (to object or to function);
- a pointer to member type (to member object or to member function);
- an enumeration type;
- std::nullptr_t; (since C++11)
And since C++20
- a floating-point type;
- a literal class type with the following properties:
- all base classes and non-static data members are public and non-mutable and
- the types of all bases classes and non-static data members are structural types or (possibly multi-dimensional) array thereof.
We can leverage this feature. Consider this struct -
template<typename T, T t>
struct Tester;What happens if we write Tester<int, 1>? After substitution, this becomes int, int 1 which is perfect. But if we do Tester<int, p> where let's say p is a int*, this fails because p is not an int. So, we see we can use this trick to tell the compiler that the second argument must have a type that agrees with the first. We can pass a pointer of the foo member and check if it's a pointer to a function returning string or not
Tester<std::string (A::*)(), &A::foo> t; // Ok. foo is a function in A
Tester<std::string (B::*)(), &B::foo> t; // Fails. foo is not a function
Tester<std::string (C::*)(), &C::foo> t; // Fails. No member named fooThe type std::string (A::*)() is a pointer to a member function of A that returns a std::string. Since A::foo matches with this type, the template works for A. Whereas for B and C it fails.
We have made progress!
template<typename T>
struct HasFoo {
template<typename U, U u> struct Tester;
template<typename C>
??? test(Tester<std::string (C::*)(), &C::foo>*) {}
template<typename>
??? test(...) {}
static const bool value = ???
};So we have made our inner test function templated that accepts a parameter C and uses the Tester struct explained above.
If, somehow, we can pass call test<T> with some parameter (that can be a pointer of course) for example test<T>(0) what will happen? See, if T has foo function, the template substitution will work and the first test will be called. If T does not have a foo function, or it's not a function returning string SFINAE will jump in, and the black hole version of foo will be called instead.
We're accepting a pointer to Tester because we want to avoid instantiating the class. It's an incomplete type anyway. The 0 doesn't matter. We could've used any integer since we just want to trick the compiler into looking at the templates. Also, we had to make the black hole version templated too, since we are calling test<T>(0) and not just test(0).
Fine, so if T has foo function, the first test is called, otherwise the black hole test is called. But how do we distinguished between them in compile time, without actually calling the function?
The answer is in an operator that is often not given importance in beginner learning - the infamous sizeof
You see, sizeof can evaluate expressions as if it was compiled, without actually evaluating it.
int hello() {
std::cout << "Hello ";
return 1;
}
int main() {
std::cout << std::boolalpha;
std::cout << (sizeof(hello()) == sizeof(int));
}This prints true and not Hello true because sizeof(hello()) doesn't actually call hello .
We can use this trick to distinguish which overload of test is called. So we just need to specify two different return types for the two overloads and we can compare their sizes in value. For that reason, we create two types -
typedef char yes[1];
typedef char no[2];yes refers to a one element char array and no refers to a two element char array. Now we can complete HasFoo -
template<typename T>
struct HasFoo {
typedef char yes[1];
typedef char no[2];
template<typename U, U u> struct Tester;
template<typename C>
static yes& test(Tester<std::string (C::*)(), &C::foo>*) {}
template<typename>
static no& test(...) {}
static const bool value = (sizeof(test<T>(0)) == sizeof(yes));
};And voila! It works just as you'd expect.
Although this solution works, it's too much of a trick and not really expressive. At one glance, you can't really tell what's going on unless already informed.
Let's see if we can leverage some modern C++ features to improve.
decltype and declval
decltype in simple words evaluates the type of an expression. It is useful when declaring types that are difficult or impossible to declare using standard notation, like lambda-related types or types that depend on template parameters. For example
template<typename T, typename U>
auto add(T t, U u) -> decltype(t + u) {
return t+u;
}Here the return type of the function is the same as the type of t+u. So we can pass any two types that can be added with + and the function's return type will be automatically adjusted.
We can use decltype in declarations too.
int i = 1;
decltype(i) j = i * 2; // j is an intdeclval is another utility since C++11 defined in <utility>. It basically converts any type to a reference type, so that we can call member functions without creating an object.
Imagine the following scenario -
struct D { int bar() { return 1;} };
struct E {
E() = delete;
char bar() { return 'a'; }
};Now suppose we want to write a template class Test which has a value member whose type is same as whatever bar returns for the type. So Test<D>::value will be of type int and Test<E>::value will be of type char.
So we might write this -
template<typename T>
struct Test {
static decltype(T().bar()) value;
};Unfortunately we can't write Test<E>::value because the default constructor of E is deleted. So we can't have E().bar() in the template.
Here we can use declval.
template<typename T>
struct Test {
static decltype(std::declval<T>().bar()) value;
};Using declval we can get the return type of T::bar without actually instantiating an object.
void_t
Inside <type_traits> lives void_t since C++17. It's job is simple, it maps a sequence of any type to the type void. It is as simple as a re-spelling of void
template< class... >
using void_t = void;It's easy. It takes as many or as few (well-formed) types you want, and just returns void.
How and where is this re-spelling of void useful? Well, you see the types we pass in must be well formed. So, we can actually use SFINAE here. For example, we can use it to detect if the type has some specific member or not. Suppose we want to know if a type T has a nested ::foo member -
struct K {
typedef int foo;
};
struct L {};
has_foo<K>::value; // true
has_foo<L>::value; // falseHere is the code for has_foo
template< class, class = std::void_t<> >
struct has_foo : std::false_type { }; // primary template
template< class T >
struct has_foo<T, std::void_t<typename T::foo>> : std::true_type { }; // Specialised templateWhat's happening here?
First we have the primary template which takes two parameters, and the second one has a default type of void which is important. It inherits from false_type so that it's ::value is false.
Next we have the specialised template. And here's the trick. When we pass A, we see that typename A::foo is well-formed. There really is a type foo inside A. Although both the templates work, the 2nd one is a better choice and is chosen.
Now if we pass B, the expression typename B::foo is not well formed, and so SFINAE kicks in and the 2nd template is thrown out.
You see, here void is actually not important. It was just a placeholder to trick the compiler into evaluating some type related expressions, and apply SFINAE.
Now, we're getting somewhere. Can we use this technique to find out if we have the foo method defined or not? Of course we can. Now typename T::foo will not work, since foo is not a type, rather a member. But we can use decltype to get its type
template< class, class = std::void_t<> >
struct has_foo : std::false_type { };
template< class T >
struct has_foo<T, std::void_t<decltype(&T::foo)>> : std::true_type { };Beautiful! But there's still two problems -
The first problem is, this is just checking the existence of foo, and not checking if it's really a function or not. So that applying this on A and B will both be true. Here are our testing structs again in case you have forgotten
struct A {
std::string foo() {
return "foo() from A";
}
};
struct B { int foo = 2; };
struct C {};
The second problem is we also want to check if foo returns string or not.
The first problem is easy to tackle. We can use decltype and declval to "emulate" calling foo and if there is no foo function, we will get SFINAE.
For the 2nd part, we can use std::is_same defined in type_traits. It is a template that takes two parameters and has a value member which is true if both the types are same (accounting for cv-qualifications), and is false otherwise
std::is_same<int, int>::value; // true
std::is_same<int, unsigned int>::value; // false
std::is_same<int, signed int>::value <<; // trueThis one is pretty easy to implement too. Here is one possible way -
template<class T, class U>
struct is_same : std::false_type {};
template<class T>
struct is_same<T, T> : std::true_type {};I will leave this up to the reader to argue why this works.
Going back to our original problem, we can compare if foo returns string or not using the is_same class
template< class, class = std::void_t<> >
struct has_foo : std::false_type { };
template< class T >
struct has_foo<T, std::void_t<decltype(std::declval<T>().foo())>>
: std::is_same<decltype(std::declval<T>().foo()), std::string> { };
decltype(std::declval<T>().foo()) gives the return type of foo. If there is no foo function, or foo is not a function, void_t gets ill-formed parameters and we face SFINAE. So this makes sure foo is a function.
Next we are inheriting from is_same which compares the return value of foo with string and if indeed foo returns string we get true_type else we get false_type.
C++20 concepts
Now C++20 introduces a new feature called concepts. Using this, we can specify the interface of a class precisely. Before we use that, let us consider what could be the use of the has_foo defined above.
One use case could be you want to have a function that calls foo on its argument only if foo exists as a member function -
template<typename T>
void bar(T t) {
// call t.foo() only if it exists
}One way we can do is to use enable_if and the has_foo defined above to have a templated version of bar that accepts proper types -
template<typename T>
std::enable_if<has_foo<T>::value, T> bar(T t) {
t.foo();
return t;
}
With the new feature concepts, you can avoid templates altogether and write the function bar so that it accepts only types with foo present.
template <typename T>
concept HasFoo = requires(T t)
{
{t.foo()} -> std::convertible_to<std::string>;
};This defines a concept named as HasFoo that is satisfied by any type which has foo as a member function and whose return type is convertible to string.
Now we can use this in the function bar
void bar(HasFoo h) { h.foo(); }And that's it! Now bar only accepts the proper types. No more tricky hacks with templates. C++20 to the rescue.
So, in this post we have looked at SFINAE, what is it's (basic) usage and used advanced features to de-complicate templates. In future posts, we will pick up one of the modern features and explain in deep.
If you liked this post, don't forget to subscribe to my blog for more.
