5

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;
}
Community
  • 1
  • 1
raymai97
  • 806
  • 7
  • 19
  • [Why is using namespace std bad practise](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Peter VARGA Apr 23 '17 at 14:46

2 Answers2

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

Nir Friedman
  • 17,108
  • 2
  • 44
  • 72
  • More modern signature would be `template void BubbleSort(Range& rng, F fnCompare, bool reverse)`. In function definition one would use `begin(rng)` and `end(rng)` to obtain iterators. – zett42 Apr 23 '17 at 15:11
  • @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. – Nir Friedman Apr 23 '17 at 15:14
  • You don't need any C++17 and not even C++14 facilities to write algorithms like this. – zett42 Apr 23 '17 at 15:19
  • @zett42 you can write it, but it's not idiomatic and not a good idea without having access to a (the) proper ranges library. – Nir Friedman Apr 23 '17 at 15:43
  • I believe the `Range& rng` version is C++11 idiomatic: `for ( auto& item : rng ) { ... }` – TBBle Apr 23 '17 at 15:52
  • Your method provides great flexibility, I like it but it seems it is not restrictive enough. In `BubbleSort()` I typed testing code `T a, b; int cmp = fnCompare(a, b);`, then I use the function like `BubbleSort(doubleArray, [](char, char){ return 0; }, false);`. It compiles. It would be great if I can assert the comparator parameter type must be the same of array data type. – raymai97 Apr 23 '17 at 15:54
  • @TBBle It is not. Look at the standard library. Consistency with the standard library is part of being idiomatic. Not to mention you will need some kind of additional boilerplate struct to operate on any sub-range of a container. The main win of ranges is not to save a handful of characters when calling a function. It is to enable composition, which is a non-trivial task, and you certainly don't get that from this simple change. – Nir Friedman Apr 23 '17 at 16:14
  • @raymai97 I agree that it's nasty that that works, but you are tracing the error to the wrong point. Implicit conversions basically say that it is safe to always convert and use the type in question. That you can use a lambda like this but not a function pointer is a *good* thing about lambdas. The problem is that the implicit conversion of int to char is a really bad idea, because its narrowing. If your comparator took 64 bit integers and you were passing 32 bit integers, I think you wouldn't mind, right? I recommend using -Wconversion compiler flag, to catch such conversions. – Nir Friedman Apr 23 '17 at 16:23
  • @NirFriedman I take your point about sub-range support, and that "Iterator Pair" is the consistent idiom in C++ STL, and the correct idiom to use here. That doesn't make the "Range" form non-idiomatic. [N4128](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html#an-iterables-end-may-have-a-different-type-than-its-begin) suggests we'll want both overloads going forward, although the implementation may not be the same as it would be for the same signature today. – TBBle Apr 23 '17 at 17:04
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.

Rakete1111
  • 47,013
  • 16
  • 123
  • 162
  • Works in GCC, but in MSVC2015 I get this error: `error C2593: 'operator +' is ambiguous, note: could be 'built-in C++ operator+(main::::)' ...` – raymai97 Apr 23 '17 at 15:35
  • @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? – Rakete1111 Apr 23 '17 at 16:27
  • @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. – chris Apr 23 '17 at 18:00