std::function instead of templates for predicates

Question

Many standard library algorithms take predicate functions. However, the type of these predicates is an arbitrary, user-provided template parameter. Why doesn't C++11 specify that these take a specific type, like std::function instead? For example:

template< class InputIt >
InputIt find_if( InputIt first, InputIt last,
             std::function<bool()> p );

Isn't using this instead of a template as argument type not much more clean?

Answer 1

std::function is for runtime polymorphism. Any particular std::function instance could be storing a functor of any type (a type that's appropriate for the std::function's signature, of course).

Standard library algorithms and such are templated on the type of their function parameters. As such, they don't need runtime polymorphism to do their job; they rely on compile-time polymorphism.

Most important of all, such algorithms don't need to force the cost of runtime polymorphism on you. If you want runtime polymorphism, you can send it a std::function or whatever. If you want compile-time polymorphism, you provide it a type that doesn't use polymorphic dispatch (aka: most functors or functions).

The cost of runtime polymorphism also includes the inability to inline the function call. Using a proper functor (or even function pointers, depending on how good your compiler is), the compiler can generally inline the function call if it so desires. With runtime polymorphism, not only are you paying the cost of the runtime dispatch (which may include additional parameter forwarding costs), you're also loosing important optimization opportunities.

Answer 2

Performance!

Template base function is very very better than std::function mode. I did this test for you:

template <typename F>
void test1(const F &f)
{
    for (unsigned long long i = 0; i < 19000000; i++)
        f();
}

void test2(function<void()> &f)
{
    for (unsigned long long i = 0; i < 19000000; i++)
        f();
}

int main()
{
    {
    LARGE_INTEGER frequency, start, end;
    double interval;
    QueryPerformanceFrequency(&frequency);
    QueryPerformanceCounter(&start);

    unsigned long long x = 0;
    test1([&x]()
    {
        x++;
    });

    QueryPerformanceCounter(&end);
    interval = (double) (end.QuadPart - start.QuadPart) / frequency.QuadPart;

    cout << "Template mode: " << interval << " " << x << endl;
    }
    {
    LARGE_INTEGER frequency, start, end;
    double interval;
    QueryPerformanceFrequency(&frequency);
    QueryPerformanceCounter(&start);

    unsigned long long x = 0;
    function<void() > f = [&x]()
    {
        x++;
    };
    test2(f);

    QueryPerformanceCounter(&end);
    interval = (double) (end.QuadPart - start.QuadPart) / frequency.QuadPart;

    cout << "std::function mode:" << interval << " " << x << endl;
    }
}

Template mode: 2.13861e-006

std::function mode:0.220006

gcc 4.7.2 on Windows7 -O2 Core2 Duo CPU 2.40GHz

Answer 3

Because std::function is imperfect.

How is it imperfect? Let me enumerate the ways.

{

First, std::function doesn't support perfect fowarding of arbitrary objects passed in to it. And, in practice, it cannot. std::function exposes one fixed signature to callers, and can accept many kinds of callees, and perfect forwarding requires a custom-crafted signature for each caller and callee. It does support perfect forwarding of exactly the arguments it exposes in its signature, but that isn't sufficient.

Imagine a std::function that takes two arguments, and int and a double. For it to do perfect forwarding, it would have to accept int&, int&& and int const&, times the same set for double (let alone volatile varients thereof). The number of signatures that each std::function has to accept to pull off perfect forwarding grows exponentially with the number of arguments it has. std::function's set of signatures it exposes (currently 1) is fixed at instantiation, while a templates set of signatures it exposes is unlimited and only generated when used. This is important because some function-like objects do optimize for these cases differently! So every std::function you have removed opportunities to perfectly forward calls to the wrapped type.

A second reason why std::function is imperfect is because compilers suck. If you wrap a lambda in a std::function then call an algorithm with it, the compiler in theory could realize that this std::function is wrapping some fixed lambda -- but in practice, it loses track of this fact, and treats the std::function as a wrapper around some generic class. So even in cases where the signature of the std::function exactly matches the use-cases of the algorithm, preventing the type-bottleneck of std::function from making the forwarding imperfect, in practice there will be overhead due to the type-erasure performed by std::function, and the compiler will find it hard to optimize over the std::function call "barrier".

A third reason why std::function is imperfect is that it would encourage algorithm writers to overly restrict what parameters can be passed in algorithms. If you examine find_if, the naive assumption is that the thing you are looking for should be the same type as the types stored in the container, or at least convertible: but the std::find_if algorithm only requires that they be comparible under the passed in functor.

This allows you to write multi-type aware functors and pass in a target object that is of an unrelated type to the type on the container, and things work just fine. Most people don't need this, and their code works find without it -- which is good as well.

The naive std::find_if would extract the underlying type of the container, and the comparison function would be between pairs of that type -- or, it would be a 4 way comparison between container types and the type of the thing being searched for. In one case, we lose flexibility -- in the other case, everyone pays for a strange corner case. And in C++, you should only pay for the features you need when you need them!

A forth reason why std::function is imperfect is that it is fundamentally a tool of type erasure. These are implementation details, but I'm not aware of a compiler which strays far from them. A std::function's purpose is expose a single signature and return value, and say "I can store anything that matches this signature and this return value, and you can call it". It exposes a static run-time interface and implementation to do this task. When you initialize a std::function, it does compile-time work to generate a helper object that wraps that particular object in the uniform std::function interface, then stores that in the pImpl pattern. All of this is work that is unnecessary if you don't need type erasure.

The standard algorithms are about writing high level code that is nearly as efficient as hand-crafted solutions. Even the cost of a pointer function call isn't required to solve most of these problems, let along a virtual call through a type erased std::function.

}; // enum

std::function is an awesome tool for callbacks, to replace boilerplate single-purpose virtual interfaces, and when you need to hide the implementation details from the caller (say, you need to cross compilation unit boundaries for design decisions).

The good news is that better solutions to this problem are coming down the pipe. In particular, one of the goals for C++14 or C++17 is that it is going to have some kind of "concept" support, where you can say "this template argument has the following properties". What the exact syntax will be is far from certain -- the C++11 Concept proposal is probably going way to far -- but there is lots of enthusiasm about it, and there is a working group on the problem right now.

When or if it is done, you'll be able to mark up the functor with meaningful concept information that says "this argument isn't just any type, but a type that is a functor that takes two values (including the contained data types), and returns a bool compatible value" that the compiler, your IDE, and you can understand without having to go to the documentation for the function.