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

Answer 1

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).

Answer 2

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.