It's because a lambda function is not a std::function<...>. The type of

auto lambda = [](const std::string& s) { return std::stoi(s); };

is not std::function<int(const std::string&)>, but something unspecified which can be assigned to a std::function. Now, when you call your method, the compiler complains that the types don't match, as conversion would mean to create a temporary which cannot bind to a non-const reference.

This is also not specific to lambda functions as the error happens when you pass a normal function. This won't work either:

int f(std::string const&) {return 0;}

int main()
{
    std::vector<int> vec;
    C<int> c;
    c.func(vec, f);
}

You can either assign the lambda to a std::function

std::function<int(const std::string&)> lambda = [](const std::string& s) { return std::stoi(s); };

,change your member-function to take the function by value or const-reference or make the function parameter a template type. This will be slightly more efficient in case you pass a lambda or normal function pointer, but I personally like the expressive std::function type in the signature.

template<typename T>
class C{
    public:
    void func(std::vector<T>& vec, std::function<T( const std::string)> f){
        //Do Something
    }

    // or
    void func(std::vector<T>& vec, std::function<T( const std::string)> const& f){
        //Do Something
    }

    // or
    template<typename F> func(std::vector<T>& vec, F f){
        //Do Something
    }
};

Stephan T. Lavavej explains why this doesn't work in this video. Basically, the problem is that the compiler tries to deduce BaseT from both the std::vector and the std::function parameter. A lambda in C++ is not of type std::function, it's an unnamed, unique non-union type that is convertible to a function pointer if it doesn't have a capture list (empty []). On the other hand, a std::function object can be created from any possible type of callable entity (function pointers, member function pointers, function objects).

Note that I personally don't understand why you would want to limit the incoming functors to that specific signature (in addition to the fact that indirection through a polymorphic function wrapper, like std::function, is by far more inefficient than a direct call to a functor (which may even be inlined)), but here's a working version. Basically, it disables argument deduction on the std::function part, and only deduces BaseT from the std::vector argument:

template<class T>
struct Identity{
  typedef T type;
};

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;
}

Live example on Ideone.

Another possible way would be to not restrict the functor type directly, but indirectly through SFINAE:

template<class T, class F>
auto f(std::vector<T> v, F fun)
    -> decltype(bool(fun(v[0])), void())
{
  // ...
}

Live example on Ideone.

This function will be removed from the overload set if fun doesn't take an argument of type T& or if the return type is not convertible to bool. The , void() makes f's return type void.