Controlling overload resolution #4: SFINAE

Overload resolution is one of C++ most complicated things and yet it works most of the time without the need to think about it. In this mini-series, I will show you how to control this complex machinery so it is even more powerful and completely under your control.

The fourth post shows you a weirdly named and powerful alternative to tag dispatching: SFINAE.

Introduction

Remember the previous post?

Thought so.

To recap we wrote a construct() function that takes a range to uninitialized memory and initializes it by calling the default constructor. Exception handling was required to ensure that types with a throwing constructor don’t leak anything. This overhead can be avoided for types with a non-throwing constructor though.

We implemented this switch with tag dispatching and ended up with something like this:

#include <new>
#include <type_traits>

template <typename T>
void construct(std::true_type, T *begin, T *end)
{
	for (auto cur = begin; cur != end; ++cur)
		::new(static_cast<void*>(cur)) T(); 
}

template <typename T>
void construct(std::false_type, T *begin, T *end)
{
	auto cur = begin;
	try
	{
		for (; cur != end; ++cur)
			::new(static_cast<void*>(cur)) T(); 
	}
	catch (...)
	{
		for (auto new_cur = begin; new_cur != cur; ++new_cur)
			new_cur->~T();
		throw;	
	}
}

template <typename T>
void construct(T *begin, T *end)
{
	construct(std::is_nothrow_default_constructible<T>{}, begin, end);
}

Based on the resulting type of std::is_nothrow_default_constructible, a different implementation is selected. Using tag dispatching for these kinds of problems is very elegant, and I would always prefer it.

But for the sake of this post, here is how the same problem could be solved using SFINAE:

#include <new>
#include <type_traits>

template <typename T,
		  typename = typename std::enable_if<std::is_nothrow_default_constructible<T>::value>::type>
void construct(T *begin, T *end)
{
	for (auto cur = begin; cur != end; ++cur)
		::new(static_cast<void*>(cur)) T(); 
}

template <typename T,
		 typename = typename std::enable_if<!std::is_nothrow_default_constructible<T>::value>::type>
void construct(T *begin, T *end)
{
	auto cur = begin;
	try
	{
		for (; cur != end; ++cur)
			::new(static_cast<void*>(cur)) T(); 
	}
	catch (...)
	{
		for (auto new_cur = begin; new_cur != cur; ++new_cur)
			new_cur->~T();
		throw;	
	}
}

This code does exactly the same. Calling construct() for - let’s say - int calls the first implementation, for a type with a throwing constructor the second one.

This looks complicated, so let’s take a step back and look at it in more detail.

Substitution failure…

Consider the following function template that erases a value from a container:

template <typename Cont>
void erase(Cont &c, const typename Cont::key_type &value)
{
	c.erase(value);
}

This function (in better) will be part of C++17’s STL as proposed by Uniform Container Erasure.

It can be called for all sets and maps in the STL (so std::map, std::unordered_set,…) and all other types that have the erase() member function that takes its typedef key_type. So what happens if you call it with a different type, let’s say std::vector<int>?

The compiler will perform template argument deduction and deduce the type of Cont to be a std::vector<int>. Then it will substitute the signature (i.e. arguments, return type) by replacing all template arguments with the deduced type, resulting in the following signature:

void erase(std::vector<int> &c, const std::vector<int>::key_type &value)

But std::vector<int> does not haved a typedef key_type! So the substitution process results in an invalid type, and §14.8.2[temp.deduct]/8 specifies:

If a substitution results in an invalid type or expression, type deduction fails. An invalid type or expression is one that would be ill-formed, with a diagnostic required, if written using the substituted arguments. […] Only invalid types and expressions in the immediate context of the function type and its template parameter types can result in a deduction failure.

This simply means “if this results in something that wouldn’t compile, type deduction fails”. The “immediate context” just means that e.g. instantiating another template that results in an error is not considered as substitution failure.

Usually it just results in a compiler error message.

…is not an error

But let’s say the function is overloaded like so:

template <typename T>
void erase(std::vector<T> &c, const T &value)
{
	c.erase(std::remove(c.begin(), c.end(), value), c.end());
}

This overload uses the Erase-remove-idiom to erase a value from a std::vector<T>.

Now the compiler needs to perform overload resolution. To do so, after name-lookup has found all functions with that name in the scope, it performs template argument deduction as described above on the function templates. After the substitution we have the following signatures:

void erase(std::vector<int> &c, const std::vector<int>::key_type &value)

void erase(std::vector<int> &c, const int &value)

The first one has an invalid expression anyway so type deduction fails. But the program compiles anyway and the compiler chooses the right overload, due to a subtle part of §14.8.3[temp.over]/1:

[…] For each function template, if the argument deduction and checking succeeds, the template-arguments (deduced and/or explicit) are used to synthesize the declaration of a single function template specialization which is added to the candidate functions set to be used in overload resolution.

“If the argument deduction and checking succeeds”, i.e. there is no type deduction failure, and only then, the function will become a candidate for overload resolution. Otherwise it won’t.

So when overloading, substition failure is not an error - SFINAE.

std::enable_if

In the erase() implementation I’ve already shown you a way to control overload resolution with SFINAE. The first overload is only considered for containers that have a key_type typedef, for others, it results in substitution failure and is not considered a candidate for overload resolution.

But how does the construct() example work?

First, let’s take a look at std::enable_if, it can be implemented like so:

template <bool B, typename T = void>
struct enable_if;

template <typename T>
struct enable_if<false, T> {};

template <typename T>
struct enable_if<true, T>
{
	using type = T;	
};

So it takes a boolean as first value and an optional type as second argument. Only if the boolean is true does it have the member typedef type.

In the example, I’ve used it like so in the template argument list:

typename = typename std::enable_if<std::is_nothrow_default_constructible<T>::value>::type

It could also be used as return type typename std::enable_if<std::is_nothrow_default_constructible<T>::value>::type construct(...) or default argument void construct(T *begin, T *end, typename std::enable_if<std::is_nothrow_default_constructible<T>::value, int>::type = 0). For that reason, the resulting type can be set appropriately.

This simply declares a defaulted template type argument without a name. The default is the type of std::enable_if<std::is_nothrow_default_constructible<T>::value>. std::is_nothrow_default_constructible<T>::value checks whether the default constructor of T is noexcept and sets the value accordingly. So if the value is true, the template argument is defaulted to std::enable_if<...>::type, which is simply void. But if it is false, there is no member typedef type in std::enable_if!

Sounds familiar, doesn’t it? This results in substitution failure, so the overload is not considered part of overload resolution.

Note that we needed the enable_if on both overloads with inverted conditions. If it only were on the first one, for types that are nothrow default constructible, both functions are candidates. And since no function is a better match, the call is ambiguous. So by putting it onto both overloads, there is only one candidate that matches in each case.

Type vs expression SFINAE

But that’s ugly. The tag dispatching version is much nicer. So why should you use SFINAE then?

The things I’ve shown you so far are all examples of type SFINAE (using a non existing member typedef/value). But since C++11 there is also expression SFINAE. expression SFINAE occurs on arbitrary expressions in the function signature.

There is a full list on cppreference.com, if you are interested in the distinction.

For example, the first overload of erase() could also be specified like so:

template <typename Cont, typename Key>
void erase(Cont &c, const Key &value, std::size_t = c.erase(value))
{
	c.erase(value);
}

The erase() member function returns a Cont::size_type, so the result can be used to initialize an unnamed parameter. If substitution of Cont makes the call invalid, expression SFINAE kicks in and ignores it from overload resolution.

But the expression is still evaluated, which is a bug! It should not be evaluated, we only want to have it somewhere in the signature. So we need a context where it is not evaluated, but still has an effect on SFINAE:

template <typename Cont, typename Key, typename = decltype(c.erase(value))>
void erase(Cont &c, const Key &value)
{
	...
}

I’ve used decltype() here. decltype() (like sizeof(), noexcept() and the like) does not evaluate the expression, it only checks its type. And since it returns the type, I’ve used a defaulted template argument again. But the above code does not compile, since the names of the arguments are not available there, so we need to create new ones:

template <typename Cont, typename Key, typename = decltype(Cont{}.erase(Key{}))>
void erase(Cont &c, const Key &value)
{
	...
}

Here I’ve created some objects to call the member function on. But Cont{} is an R-value so it may not be possible to call erase() on it. Also, SFINAE kicks in more than we want: If there is no default constructor, the candidate will also fail!

So we need to use std::declval:

template <typename Cont, typename Key, typename = decltype(std::declval<Cont>().erase(std::declval<Key>()))>
void erase(Cont &c, const Key &value)
{
	...
}

std::declval<T> is a helper function that simply returns a T&.

The actual type is slightly more complicated, but that’s not important here.

How does it create that T? It doesn’t, it has no definition! It is only meant to be used in the unevaluated contexts like decltype(), so it does not need one, since it will be never called.

So using expression SFINAE it is possible to disregard templated overloads based on the existence of member functions or the validity of any other arbitrary expression.

Note that especially older MSVC versions have lots of problems with expression SFINAE. It is a nightmare to port it.

void_t

But the decltype() stuff is still ugly.

One solution is to use a macro:

#define SFINAE(Expr) decltype((Expr), int()) = 0

It can be used like so:

template <typename Cont, typename Key>
void erase(Cont &c, const Key &value, SFINAE(c.erase(value)))
{
	...
}

It will be expanded into an unnamed, defaulted parameter of type int due to the comma operator.

The expression passed to decltype() is (Expr),int(), the result of a,b is b, so the type is int. The comma operator is awesome.

But there is another alternative that does not use macros, this tiny little alias template:

template <typename ... Ts>
using void_t = void;

This will simply become void, no matter what the arbitrary number of types are.

Some compilers are too smart and will not look at the Ts there, so it is often better to do something like this:

template <typename...>
struct voider
{
	using type = void;
};

template <typename ... Ts>
using void_t = typename voider<Ts...>::type;

Since they cannot now if voider is specialized, they will have to look at them.

What’s the purpose, you ask?

Well, void_t can consume arbitrary decltype() expressions and makes them void:

template <typename Cont, typename Key>
auto erase(Cont &c, const Key &value) -> void_t<decltype(c.erase(value))>

Note the use of the trailing return type to access the parameter names in decltype().

This does not seem very useful here, but is especially useful for controlling template specializations with SFINAE (a topic of a future blog post).

And with C++17, void_t will become std::void_t.

Conclusion

SFINAE allows you to disregard certain function templates from overload resolution if their signature contains expressions that are not well-formed if the types are substituted.

This allows selecting implementation based on arbitrary conditions (like the existence of member functions) and is a very powerful feature.

Since it is somewhat unreadable, I do not recommend it when tag dispatching can be used (like using it with std::enable_if).

In the next post of the series, I will combine everything I’ve shown you so far to implement something very powerful: The default specialization of memory::allocator_traits of foonathan/memory.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.