C++11 does not deduce type when std::function or lambda functions are involved

When I define this function,

template<class A>
set<A> test(const set<A>& input) {
    return input;
}

I can call it using test(mySet) elsewhere in the code without having to explicitly define the template type. However, when I use the following function:

template<class A>
set<A> filter(const set<A>& input,function<bool(A)> compare) {
    set<A> ret;
    for(auto it = input.begin(); it != input.end(); it++) {
        if(compare(*it)) {
            ret.insert(*it);
        }
    }
    return ret;
}

When I call this function using filter(mySet,[](int i) { return i%2==0; }); I get the following error:

error: no matching function for call to ‘filter(std::set&, main()::)’

However, all of these versions do work:

std::function<bool(int)> func = [](int i) { return i%2 ==0; };
set<int> myNewSet = filter(mySet,func);

set<int> myNewSet = filter<int>(mySet,[](int i) { return i%2==0; });

set<int> myNewSet = filter(mySet,function<bool(int)>([](int i){return i%2==0;}));

Why is c++11 unable to guess the template type when I put the lambda function directly inside the expression without directly creating a std::function?

EDIT:

Per advice of Luc Danton in the comments, here is an alternative to the function I had earlier that does not need the templates to be passed explicitly.

template<class A,class CompareFunction>
set<A> filter(const set<A>& input,CompareFunction compare) {
    set<A> ret;
    for(auto it = input.begin(); it != input.end(); it++) {
        if(compare(*it)) {
            ret.insert(*it);
        }
    }
    return ret;
}

This can be called by set<int> result = filter(myIntSet,[](int i) { i % 2 == 0; }); without needing the template.

The compiler can even guess the return types to some extent, using the new decltype keyword and using the new function return type syntax. Here is an example that converts a set to a map, using one filtering function and one function that generates the keys based on the values:

template<class Value,class CompareType,class IndexType>
auto filter(const set<Value>& input,CompareType compare,IndexType index) -> map<decltype(index(*(input.begin()))),Value> {
    map<decltype(index(*(input.begin()))),Value> ret;
    for(auto it = input.begin(); it != input.end(); it++) {
        if(compare(*it)) {
            ret[index(*it)] = *it;
        }
    }
    return ret;
}

It can also be called without using the template directly, as

map<string,int> s = filter(myIntSet,[](int i) { return i%2==0; },[](int i) { return toString(i); });

Solution 1:

The issue is on the nature of lambdas. They are function objects with a fixed set of properties according to the standard, but they are not a function. The standard determines that lambdas can be converted into std::function<> with the exact types of arguments and, if they have no state, function pointers.

But that does not mean that a lambda is a std::function nor a function pointer. They are unique types implementing operator().

Type deduction, on the other hand, will only deduce exact types, with no conversions (other than const/volatile qualifications). Because the lambda is not a std::function the compiler cannot deduce the type in the call: filter(mySet,[](int i) { return i%2==0; }); to be any std::function<> instantiation.

As of the other examples, in the first one you convert the lambda to the function type, and then pass that. The compiler can deduce the type there, as in the third example where the std::function is an rvalue (temporary) of the same type.

If you provide the instantiating type int to the template, second working example, deduction does not come into play the compiler will use the type and then convert the lambda to the appropriate type.

Solution 2:

Forget about your case. as that is too complex for analysis.

Take this simple example:

 template<typename T>
 struct X 
 {
     X(T data) {}
 };

 template<typename T>
 void f(X<T> x) {}

Now call f as:

 f(10); 

Here you might be tempted to think that T will be deduced to int and therefore, the above function call should work. Well, that is not the case. To keep thing simple, imagine that there is another constructor which takes int as:

 template<typename T>
 struct X 
 {
     X(T data) {}
     X(int data) {} //another constructor
 };

Now what T should be deduced to, when I write f(10)? Well, T could any type.

Note that there could be many other such cases. Take this specialization, for instance:

 template<typename T>
 struct X<T*>         //specialized for pointers
 {
    X(int data) {}; 
 };

Now what T should be deduced to for the call f(10)? Now it seems even harder.

It is therefore non-deducible context, which explains why your code doesn't work for std::function which is an identical case — just looks complex at the surface. Note that lambdas are not of type std::function — they're basically instances of compiler generated classes (i.e they're functors of different types than std::function).