lambda expression and template deduction against std::function: why this works?

Question

My question is somewhat related to this question: Lambdas and std::function. Please read this question and its accepted answer.

So, the accepted answer says that the following code makes template parameter deducing against lambdas succeed, but why?

template<class T>
struct Identity{
  typedef T type;//why this helps?
};

template<typename BaseT>
vector<BaseT> findMatches(vector<BaseT> search, 
    typename Identity<function<bool (const BaseT &)>>::type func)
{
    vector<BaseT> tmp;

    for(auto item : search)
    {
        if( func(item) )
        {
            tmp.push_back(item);
        }
    }

    return tmp;
}

void Lambdas()
{
    vector<int> testv = { 1, 2, 3, 4, 5, 6, 7 };

    auto result = findMatches(testv, [] (const int &x) { return x % 2 == 0; });//lambda here.

    for(auto i : result)
    {
        cout << i << endl;
    }
}

int main(int argc, char* argv[])
{

    Lambdas();

    return EXIT_SUCCESS;
}

The code above is working, but I don't know why. Firstly, I know the template deduction of BaseT does not happen for lambda because that's a non-deducible context(Identify<function<bool (const BaseT &)>>::type). Instead, BaseT is deduced from testv as int, and template parameter substitution happens in Identity<function<bool (const BaseT &)>>::type.

But what's next? after substitution, Identity<function<bool (const BaseT &)>>::type becomes function<bool (const BaseT &)>, but isn't lambda expression not of that type, and conversions does not happen in template parameter deduction(although here is template parameter substitution)?

Thanks for your explaining! P.S. I seem to know compiler generate unique-named class for each lambda expression. So why lambda can match with function<bool (const BaseT &)>?

Answer 1

But what's next? after substitution, Identity<function<bool (const BaseT &)>>::type becomes function<bool (const BaseT &)>, but isn't lambda expression not of that type, and conversions does not happen in template parameter deduction(although here is template parameter substitution)?

You're correct that there is no subisitution during template argument deduction but once that has been completed we treat the function call as calling the instantiated function. That means Identity<function<bool (const BaseT &)>>::type has been substituted with function<bool (const BaseT &)> your instantiated function you are calling is:

vector<int> findMatches(vector<int> search, function<bool (const int&)> func)

Since it is taking a concrete function<bool (const int&)> the lambda can be using to construct func