Why could not deduce template argument when passing lambda instead of function pointer

Question

I have a bubble-sort function that takes an array, a compare function, and a boolean that indicates if it should sorts the array upside-down. It is a template function that supports any data-type, and will deduce array size automatically.

When specifying the compare function, if I pass function pointer, the compiler will deduce the data type of array automatically, which is great. But if I pass a lambda instead, it will not deduce automatically. I have to specify the data type explicitly, or static_cast the lambda as fnCompare_t<double>.

What is the reason behind this? Because according to this post, as long as the lambda doesn't capture, it can be used like the plain-old function pointer, but it seems it is not always the case? How come it can be different in this case?

#include <iostream>
using namespace std;

template <typename T>
using fnCompare_t = int(*)(T const &, T const &);

template <typename T, size_t count>
inline void BubbleSort(
    T(&array)[count],
    fnCompare_t<T> fnCompare,
    bool reverse)
{
    cout << "TODO: Implement BubbleSort" << endl;
}

double doubleArray[] = {
    22.3, 11.2, 33.21, 44.2, 91.2, 15.2, 77.1, 8.2
};

int CompareDouble(double const & a, double const & b)
{
    return a > b ? 1 : a == b ? 0 : -1;
}

int main()
{
    auto fnCompare = [](double const & a, double const & b) -> int {
        return a > b ? 1 : a < b ? -1 : 0;
    };
    // compile OK:
    BubbleSort(doubleArray, CompareDouble, false);
    BubbleSort(doubleArray, static_cast<fnCompare_t<double>>(fnCompare), false);
    BubbleSort<double>(doubleArray, fnCompare, false);
    // compile error, could not deduce template argument:
    //BubbleSort(doubleArray, fnCompare, false);
    return 0;
}

Why is using namespace std bad practise

Peter VARGA
– Peter VARGA

2017-04-23 14:46:26 +00:00
Commented Apr 23, 2017 at 14:46 — Peter VARGA
– Peter VARGA, Commented Apr 23, 2017 at 14:46

Nir Friedman · Accepted Answer · 2017-04-23 14:50:14Z

7

The reason why is because you can't get an implicit conversion on a templated parameter when using deduction. The classic example is:

template <class T>
T min(T x, T y);

Calling this function as min(1, 3.0) will result in a failure. Because for both arguments, it tries to find a T to get a perfect match, and fails. If you specify the template parameter explicitly it can work: min<double>(1, 3.0). The same is true in your example, if you specify T explicitly it will work.

The idiomatic way to write the signature for your function is:

template <typename Iter, typename F>
inline void BubbleSort(
    Iter b, Iter e,
    F fnCompare,
    bool reverse)

However, this discards the compile time length information. If you want to keep that, you can do:

template <typename T, size_t count, typename F>
inline void BubbleSort(
    T(&array)[count],
    F fnCompare,
    bool reverse);

Though you should at least consider using std::array instead of a C style array which will make the signature a bit less ugly and has other benefits.

This may seem odd as we are not "verifying" the comparator having the correct signature, in the signature of our sort. But this is normal in C++, if the comparator is incorrect then it will fail at the point of usage and it will still be a compile time error. Note as well when you try to depend on a lambda implicitly converting into a function pointer, you are being unnecessarily restrictive: lambdas only convert into function pointers with identical signature. Even if the output of the lambda is implicitly convertible to the output of the function pointer, your lambda will not implicitly convert, even though the lambda can still be used!

As a final final note, it's usually better to pass functors because it's better for performance. Comparators are usually small functions and often will get inlined. But in your version, the comparator will not typically be inlined, in mine it will (because I preserve the original type of the lambda, and you do not).

answered Apr 23, 2017 at 14:50

Nir Friedman

17.9k2 gold badges48 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

zett42 Over a year ago

More modern signature would be template <typename Range, typename F> void BubbleSort(Range& rng, F fnCompare, bool reverse). In function definition one would use begin(rng) and end(rng) to obtain iterators.

Nir Friedman Over a year ago

@zett42 It's tagged C++14. Even if it wasn't, C++17 was only just standardized, and it's not likely used in prod in hardly any places. And ranges is not even standardized in 17! This is the correct, modern, standard signature, at least for the next 3 years, even for people on the bleeding edge.

zett42 Over a year ago

You don't need any C++17 and not even C++14 facilities to write algorithms like this.

Nir Friedman Over a year ago

@zett42 you can write it, but it's not idiomatic and not a good idea without having access to a (the) proper ranges library.

TBBle Over a year ago

I believe the Range& rng version is C++11 idiomatic: for ( auto& item : rng ) { ... }

|

Rakete1111 · Accepted Answer · 2017-04-23 14:59:01Z

3

You need to explicitly cast the lambda to a function pointer. There is no other way around it. But, instead of static_casting you can apply + to the lambda, which would trigger the function pointer conversion, as you can apply + to a pointer type:

BubbleSort(doubleArray, +fnCompare, false);
//                      ^^
//     applying unary + invokes the function pointer conversion operator

The reason for why there is no implicit call to the conversion operator is that during overload resolution, the compiler will only consider templates that match perfectly (see this for more info). Because a lambda is not a function pointer, there cannot be a perfect match, and the overload is discarded.

answered Apr 23, 2017 at 14:59

Rakete1111

49.5k19 gold badges133 silver badges173 bronze badges

3 Comments

raymai97 Over a year ago

Works in GCC, but in MSVC2015 I get this error:

error C2593: 'operator +' is ambiguous, note: could be 'built-in C++ operator+(main::<lambda_2d5f9fb0f6725604b096dd7e38b1690b>::<lambda_typedef_cdecl>)' ...

Rakete1111 Over a year ago

@raymai97 That's bad. VS2015 has not a very good C++11/14 support, which could explain that ambiguity. Maybe it is fixed in VS 2017?

Qaz Over a year ago

@raymai97, Pretty sure that's because MSVC has something going on with calling conventions and lambdas so that you can use them as winapi callbacks and whatnot.

Collectives™ on Stack Overflow

Why could not deduce template argument when passing lambda instead of function pointer

2 Answers 2

9 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related