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?

Just a small note on the function arguments - you'll observe that std::lower_bound (which you are reimplementing) takes a pair of iterators rather than a container as its argument. This allows it to work with any kind of container, or a subset of a container, or even ranges the Standard Library designers haven't yet thought of. When you have your code working over std::vector I strongly advise looking to make it more general in this way; I promise you'll learn something! — Toby Speight
– Toby Speight, Commented Oct 25, 2016 at 8:49
@TobySpeight he would need more than just a predicate. The predicate must be an order relationship and he needs a target value on top of that — Rerito
– Rerito, Commented Oct 25, 2016 at 9:14
Er, I meant std::find_if(), not std::lower_bound(). Both are instructive, and implementing your own is good exercise, so the rest still stands. — Toby Speight
– Toby Speight, Commented Oct 25, 2016 at 9:18
@Evgeniy definitely don't. This is already a template, there's nothing to gain with type erasure here. — Quentin
– Quentin, Commented Oct 25, 2016 at 12:12

rocambille · Accepted Answer · 2016-10-25 13:00:10Z

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.

Thanks! I think this is slightly less strict than what I intended. For example, your approach would allow to pass a vector of ints and a predicate that maps a char (not an int) to a bool. Probably doesn't matter for my use case, though.
If you're doing such things as passing an int to a predicate that takes a char, your compiler should complain about precision loss. If it is not, change your compiler ;)
Stateless lambdas will convert to function pointers though. The example from the question would compile if it weren't for the template parameter T. The answer is misleading in this regard, imho.
May I suggest adding a 4th example: call_predicate<double>(42.0, ... . It's not that templates don't work, it's Template Argument Deduction which fails here.

Community · Accepted Answer · 2017-05-23 10:32:59Z

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

@david how is static cast more readable? There is more to read, but all of it is repeating what is said right next to it. Magic that works reliably need not spell itself out.
more to read != less readable. magical features that only C++ gurus can understand (such as + and lambda functions) == not readable.
I really like the "+" magic, but I just realized that lambdas cannot be cast to function pointers if they capture local variables. Nonetheless, I learned a lot from your answer.
@DavidHaim Lambdas are not "magical features that only C++ gurus can understand". Anyone who programs in C++ should be familiar with lambdas at this point. + decaying a lambda is admittedly magical, but if you don't know what it does, it doesn't really matter. If you look at the line, it actually does what it seems to do if you don't understand the magic. How it does it is magical, but the non-guru has no need to know the magic to understand the line. You no more need to know how + works than you need to understand vectorization to write a fast for() loop.
Lambdas are indeed fundamental and there is no argue about it. the use of + as a lambda to function converter is very specific and non common. I simply see no reason use something that most of the C++ developers don't really know rather the very known and common static_cast . but I guess I won't convince you

Yakk - Adam Nevraumont · Accepted Answer · 2016-10-25 14:07:38Z

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.

Rerito · Accepted Answer · 2016-10-25 13:53:11Z

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.

Do not repeatedly forward a predicate when calling it. The first time you forward it you are making a promise not to call it again. Remove the forward to fix this; detecting the last iteration and conditionally forwarding (while correct) is going to make the code ugly for little yield.
Switching to std::function will not solve the problem here.
@ComicSansMS Sorry, the sentence was misleading... Edited it for clarity's sake
@Rerito Sorry, but I think it's still misleading. Switching to std::function allows me to pass stateful lambdas (just as the first solution with the Predicate template argument did). But it does not address the issue from the question at all: The fact that template argument deduction fails if I bury the T deep enough in the parameter type. This happens with both the function pointer and the std::function approach.
@ComicSansMS I don't think I fully get what you mean. Could you provide an example for my own instruction?

Akaedintov · Accepted Answer · 2016-10-25 08:51:35Z

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)

This has an overhead that may not be desirable. Note that the standard library doesn't do this because there is no need. You can add a template parameter for the predicate instead.
Of course you can assign a stateless lambda to a function pointer like this. Proof on coliru. It's the unspecified template argument that ruins it. Switching to std::function also doesn't solve the problem here, as long as you leave the T unspecified.

Collectives™ on Stack Overflow

Passing a lambda into a function template

5 Answers 5

6 Comments

7 Comments

Comments

8 Comments

2 Comments

Linked

Hot Network Questions