Understanding SFINAE

The SFINAE Gnomes

What is SFINAE and why do we care? SFINAE(Substitution Failure Is Not An Error) is an acronym that was first introduced by David Vandevoorde to describe the compiler’s process of eliding from the overload resolution set any template where a type substitution error would occur. Let’s take  a look at the following program I shamelessly stole from boost’s documentation:

int negate(int i){ return -i; }
template <typename T>
typename T::result_type negate(T const &t)
{
    return -t();
}

Let’s suppose you call negate(10), even though the first negate would be a good match, the compiler has to also take into consideration the second templated version and try to instantiate it with int, generating the following code:

int::result_type negate(int const &t)
{
    return -t();
}

Without SFINAE, the generated code would cause a compiler error since “int” doesn’t have a “result_type” member but fortunately we do, so the problematic overload is silently ignored by the compiler. As you will see, there are a few interesting and unexpected ways to use SFINAE. In the following example, we’ll check if a type is a container by checking if it has a iterator member with SFINAE via a technique called “the sizeof trick”.

First we need a type of some size, let’s take char:

typedef char true_type;

Then we need a type of some other size, it could be anything as long as its size is greater than the other we chosen before. An easy way to ensure it is to simply make a structure containing an array of more than one of the other type.

struct false_type{ true_type _[2]; };

Now, we need a function with two overloads, one that will be called if the type passed contains an iterator, returning our true_type and another one that will be called when it doesn’t, obviously returning our false_type.

template <typename T>
true_type has_iterator_checker(typename T::iterator *);

template <typename T>
false_type has_iterator_checker(...);

In the preceding code snippet, our good match is a function taking a iterator pointer as parameter and returning our true_type. Our worst match is the last match possible by the C++ conversion rules, the evil ellipsis, returning our false_type. As you probably already remarked, you just need the function signatures because those functions are actually never going to be called since everything is done at compilation. Now, it’s time to assemble the parts of the puzzle:

#include <iostream>
#include <vector>

typedef char true_type;
struct false_type{ true_type _[2]; };

template <typename T>
true_type has_iterator_checker(typename T::iterator *);

template <typename T>
false_type has_iterator_checker(...);

#define IS_CONTAINER(x) (sizeof(has_iterator_checker<x >(0)) == sizeof(true_type))

int main()
{
    std::cout << "Is container (int): "
              << IS_CONTAINER(int) << std::endl;
    std::cout << "Is container (std::vector<int>): "
              << IS_CONTAINER(std::vector<int>) << std::endl;
}

The only thing we haven’t seen yet in this code is the IS_CONTAINER macro. It compares the size of the type returned by the most compatible overload chosen by the compiler to our true_type. If the chosen overload returns true_type then our type is a container. We can now check if a type is a container at compile time. Our current solution is nice and functional but could really use better packaging. I’ll spare you the details and simply paste the code below:

template <typename T>
class is_container
{
    typedef char true_type;
    struct false_type{ true_type _[2]; };
    template <typename U>
    static true_type has_iterator_checker(typename U::iterator *);
    template <typename U>
    static false_type has_iterator_checker(...);
public:
    enum { value = (sizeof(has_iterator_checker<T>(0)) ==
                    sizeof(true_type)) };
};

Hurray! No more macros and we can easily check if a type is a container by simply doing is_container<my_type>::value. We’re now the proud owners of a nice little is_container class and of a bit more knowledge about SFINAE. Time to put that class to good use, but before, we will need another SFINAE trick to enable or disable code based on a condition. A very simple code that opens up a lot of possibilities:

template <bool Cond, class T = void>
struct enable_if
{
    typedef T type;
};

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

To help explaining how it works, here’s a small usage example:

template <typename T>
typename enable_if<some_boolean_condition>::type
    foo(T const &t)
{
    std::cout << t << std::endl;
}

The enable_if template takes two parameters, a boolean condition and a return type, which is “void” by default, that is simply the one the function would return if we didn’t use the template. What’s important in that template and where the magic happens is the ::type part. If “some_boolean_condition” is true, then ::type returns the return type specified and the function is instantiated normally. If “some_boolean_condition” is false, the specialization enable_if<false, T> will be used and since it doesn’t have a ::type member, a substitution failure will occur causing the compiler to silently ignore the function.

With these new SFINAE based tools in our toolbox, we can easily make static dispatching based on the property of a type as you will see in the next example:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

/*enable_if and is_container should be here*/

template <typename T>
typename enable_if<!is_container<T>::value>::type
    super_print(T const &t)
{
    std::cout << t << std::endl;
}

template <typename T>
typename enable_if<is_container<T>::value>::type
    super_print(T const &t)
{
    typedef typename T::value_type value_type;
    std::copy(t.begin(),
              t.end(),
              std::ostream_iterator<value_type>(std::cout, ", "));
    std::cout << std::endl;
}

int main()
{
    super_print(10);
    std::vector<int> b;
    b.push_back(1);
    b.push_back(2);
    b.push_back(3);
    super_print(b);
}

That simple code resumes everything we learned so far to allow easy printing of variables and containers. Without using enable_if, there would be an ambiguity since they both have the signature “void(T const &)” but having enable_if, we can enable or disable either template overload depending on the fact that it contains an “iterator” member or not, solving the issue.

That’s it for today, as you saw, SFINAE is yet another of C++’s hidden powers giving you the opportunity to make things that the language wasn’t designed for.

About these ads

6 comments so far

  1. jimmyhc on

    Second super_print function is missing a ; on the line:

    typedef typename T::value_type value_type

    • systemfault on

      True, thanks :)

  2. QBziZ on

    To be really really nitpicky :

    This :

    >> typedef char true_type;
    >> struct false_type{ char _[2]; };

    Would be a little more orthogonal when written like this :

    typedef char true_type;
    struct false_type{ true_type _[2]; };

    • systemfault on

      I’ll change it, thank you

  3. Martin P on

    Ta. Top article.
    Liked it. It out the polish on my understanding.

  4. Colin on

    In your is_container example, why not replace:

    enum { value = (sizeof(has_iterator_checker(0)) == sizeof(true_type)) };

    with…

    static const bool value = (sizeof(has_iterator_checker(0)) == sizeof(true_type));

    compilers will optimize this out to just become true or false, and it’s type safe.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: