Passing a lambda into a function template

Question

I'm learning C++, and I'm trying to implement a binary search function that finds the first element for which a predicate holds. The function's first argument is a vector and the second argument is a function that evaluates the predicate for a given element. The binary search function looks like this:

template <typename T> int binsearch(const std::vector<T> &ts, bool (*predicate)(T)) {
    ...
}

This works as expected if used like this:

bool gte(int x) {
    return x >= 5;
}

int main(int argc, char** argv) {
    std::vector<int> a = {1, 2, 3};
    binsearch(a, gte);
    return 0;
}

But if I use a lambda function as a predicate, I get a compiler error:

search-for-a-range.cpp:20:5: error: no matching function for call to 'binsearch'
    binsearch(a, [](int e) -> bool { return e >= 5; });
    ^~~~~~~~~
search-for-a-range.cpp:6:27: note: candidate template ignored: could not match 'bool (*)(T)' against '(lambda at
      search-for-a-range.cpp:20:18)'
template <typename T> int binsearch(const std::vector<T> &ts,
                          ^
1 error generated.

The above error is generated by

binsearch(a, [](int e) -> bool { return e >= 5; });

What's wrong? Why is the compiler not convinced that my lambda has the right type?

Answer 1

Your function binsearch takes a function pointer as argument. A lambda and a function pointer are different types: a lambda may be considered as an instance of a struct implementing operator().

Note that stateless lambdas (lambdas that don't capture any variable) are implicitly convertible to function pointer. Here the implicit conversion doesn't work because of template substitution:

#include <iostream>

template <typename T>
void call_predicate(const T& v, void (*predicate)(T)) {
    std::cout << "template" << std::endl;
    predicate(v);
}

void call_predicate(const int& v, void (*predicate)(int)) {
    std::cout << "overload" << std::endl;
    predicate(v);
}

void foo(double v) {
    std::cout << v << std::endl;
}

int main() {
    // compiles and calls template function
    call_predicate(42.0, foo);

    // compiles and calls overload with implicit conversion
    call_predicate(42, [](int v){std::cout << v << std::endl;});

    // doesn't compile because template substitution fails
    //call_predicate(42.0, [](double v){std::cout << v << std::endl;});

    // compiles and calls template function through explicit instantiation
    call_predicate<double>(42.0, [](double v){std::cout << v << std::endl;});
}

---

You should make your function binsearch more generic, something like:

template <typename T, typename Predicate>
T binsearch(const std::vector<T> &ts, Predicate p) {

    // usage

    for(auto& t : ts)
    {
        if(p(t)) return t;
    }

    // default value if p always returned false

    return T{};
}

Take inspiration from standard algorithms library.

Answer 2

The lambda expression with empty capture list could be implicitly converted to a function pointer. But the function pointer predicate is taking T as its parameter, that need to be deduced. Type conversion won't be considered in template type deduction, T can't be deduced; just as the error message said, candidate template (i.e. binsearch) is ignored.

You can use operator+ to achieve this, it'll convert lambda to function pointer, which will be passed to binsearch later and then T will be successfully deduced^[1].

binsearch(a, +[](int e) -> bool { return e >= 5; });
//           ~

Of course you could use static_cast explicitly:

binsearch(a, static_cast<bool(*)(int)>([](int e) -> bool { return e >= 5; }));

Note if you change predicate's type to be independent of T, i.e. bool (*predicate)(int), passing lambda with empty capture list would work too; the lambda expression will be converted to function pointer implicitly.

---

Another solution is changing the parameter type from function pointer to std::function, which is more general for functors:

template <typename T> int binsearch(const std::vector<T> &ts, std::function<bool (typename std::vector<T>::value_type)> predicate) {
    ...
}

then

binsearch(a, [](int e) -> bool { return e >= 5; });

---

^{[1] A positive lambda: '+[]{}' - What sorcery is this?}

Answer 3

Why is the compiler not convinced that my lambda has the right type?

Template functions being told to deduce their template parameters do no conversion. A lambda is not a function pointer, so there is no way to deduce the T in that argument. As all function arguments independently deduce their template parameters (unless deduction is blocked), this results in an error.

There are a number of fixes you can do.

You can fix the template function.

template <class T>
int binsearch(const std::vector<T> &ts, bool (*predicate)(T))

Replace the function pointer with a Predicate predicate or Predicate&& predicate and leave the body unchanged.

template <class T, class Predicate>
int binsearch(const std::vector<T> &ts, Predicate&& predicate)

Use deduction blocking:

template<class T>struct tag_t{using type=T;};
template<class T>using block_deduction=typename tag_t<T>::type;
template <class T>
int binsearch(const std::vector<T> &ts, block_deduction<bool (*)(T)> predicate)

optionally while replacing the function pointer with a std::function<bool(T)>.

You can fix it at the call site.

You can pass T manually binsearch<T>(vec, [](int x){return x<0;}).

You can decay the lambda to a function pointer with putting a + in front of it +[](int x) ... or a static_cast<bool(*)(int)>( ... ).

The best option is Predicate one. This is also what standard library code does.

We can also go a step further and make your code even more generic:

template <class Range, class Predicate>
auto binsearch(const Range &ts, Predicate&& predicate)
-> typename std::decay< decltype(*std::begin(ts)) >::type

The -> typename std::decay ... trailing return type part can be eliminated in C++14.

A benefit to this is that if the body also uses std::begin and std::end to find begin/end iterators, binsearch now supports deques, flat C-style arrays, std::arrays, std::strings, std::vectors, and even some custom types.

Answer 4

If you have any control over binsearch I suggest you refactor it:

template <typename T, typename Predicate>
int binsearch(std::vector<T> const& vec, Predicate&& pred) {
    // This is just to illustrate how to call pred
    for (auto const& el : vec) {
        if (pred(el)) {
            // Do something
        }
    }
    return 0; // Or anything meaningful
}

---

Another way for you is to perform type-erasure on your functor objects/function pointers/whatever... by embedding them into an std::function<bool(T const&)>. To do so, just rewrite the function above as:

template <typename T>
int binsearch(std::vector<T> const& vec, std::function<bool(T const&)> pred);

But since template argument deduction does not do any conversion, you need to explicitly feed your function like the following:

auto my_predicate = [](int x) { return true; }; // Replace with actual predicate
std::vector<int> my_vector = {1, 2, 3, 4};
binsearch(my_vector, std::function<bool (int const&)>(my_predicate));

However given the description of your function, it seems it does the same job as std::find_if.

std::vector<int> my_vector = {1, 12, 15, 13, 16};
auto it = std::find_if(std::begin(my_vector), std::end(my_vector),
                       [](int vec_el) { return !vec_el%5; });
// it holds the first element in my_vector that is a multiple of 5.
if (it != std::end(my_vector)) {
    std::cout << *it << std::endl; // prints 15 in this case
}

Note that to do a binary search, you need more than just a predicate: you need a predicate that defines an order on your range AND a target value.

Answer 5

A function pointer and a lambda function is not the same thing.

An object t can not be assigned to predicate where:

 bool (*predicate)(int)

and

auto t = [](int e) -> bool { return e >= 5; });

Might as well use std::function<bool(int)>. Your signature will look like this:

template <typename T> 
int binsearch(const std::vector<T> &ts, std::function<bool(T)> predicate){
   // ...
}

Now that's not a function pointer, You'll need to bind your founction pointers if they are necessary, (I assume you're fine with just lambdas)