CODEWITHSUNDEEP
c++
SoulerTsai
SoulerTsai

Reputation: 87

Does Comparison Function specified with lambda function in std::sort return bool type?

I was reading this code (source):

#include <iostream> 
#include <functional>
#include <algorithm>
using namespace std; 

int main() { 
    int number[] = {3, 5, 1, 6, 9};
    auto print = [](int n) { cout << n << " "; };

    sort(begin(number), end(number), [](int n1, int n2) { return n2 - n1; });
    // result: 9 6 1 5 3
    for_each(begin(number), end(number), print);
    cout << endl;

    sort(begin(number), end(number), [](int n1, int n2) { return n1 - n2; });
    // result: 3 5 1 6 9
    for_each(begin(number), end(number), print);
    cout << endl;

    return 0; 
}

And I am confused about how return n2 - n1; vs return n1 - n2; work.

According to std::sort - cppreference.com, it says the comp is a bool type function. And in C++, non-zero numbers always have true value (according to Do negative numbers return false in C/C++? - Stack Overflow).

So the number in the example above has different items inside will always cause two of those lambda functions to return true. That is to say, those lambda functions return same results in this case. But the result show that one is in the reversed order and one is in the original order.

How can I explain this or what do I miss?

Upvotes: 2

Views: 588

Answers (3)

prehistoricpenguin
prehistoricpenguin

Reputation: 6326

The std::sort implementation in libstdc++ has optimized for a short sequence, after checking the source, we know that for a small sequence short than 16 elements, it will fall back to insertion sort.

In c++, the non-zero number can be automatically converted into a bool value true, with insertion sort, if your sequence has no identical values, it will be reversed(In the insertion sort loop, all values will be moved to the first place, then once loop finished, the sequence is reverted).

It's not a deterministic behavior, since the STL implementation may differ from each other, and the _S_threshold number is unrevealed to the end user.

Enlarge the array to be more than 16 elements, we get totally different result:

The program crashed with buffer overflow! So now we proved it was wrong to use such kinds of lambda [](int n1, int n2) { return n2 - n1; }, the correct way should be sort(begin(number), end(number), [](int n1, int n2) { return n2 > n1; });

#include <iostream> 
#include <functional>
#include <algorithm>
using namespace std; 

int main() { 
    int number[] = {3, 5, 1, 6, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23};
    auto print = [](int n) { cout << n << " "; };

    sort(begin(number), end(number), [](int n1, int n2) { return n2 - n1; });

    for_each(begin(number), end(number), print);
    cout << endl;

    sort(begin(number), end(number), [](int n1, int n2) { return n1 - n2; });

    for_each(begin(number), end(number), print);
    cout << endl;


    return 0; 
}

Upvotes: 2

rawrex
rawrex

Reputation: 4064

The n2 - n1 in the case of a negative number as a result when converted to bool will yield true. So n1 turns out to be less than n2. That's why it is a bad practice to use ints in such Boolean context.

Yes, as stated in the documentation:

...comparison function object which returns ​true if the first argument is less than the second

But the implementation of the comparison here leads to failure. Try this and see for yourself:

int x = 5, y = 555;
bool b = x - y;
std::cout << b << std::endl; // Prints 1, means true

The supplied comparison function must follow the logic of the operator<. So, when your lambda has n1 = 5, n2 = 1; the result of n2 - n1 is -4 which when used in Boolean context (bool is unsigned) is converted to 1.

As a result you have 5 < 1 is true.

While in your output 1 is placed after 5, this kind of erroneous comparison leads to undesired overall result.

Upvotes: 1

Ross Smith
Ross Smith

Reputation: 3765

The comparison functions used here are invalid. The function passed to sort() is supposed to return true if the LHS comes before RHS in the intended sort order, false otherwise (i.e. it should behave like "less than"). Neither of the lambdas here behaves like this, so calling sort() with either of those functions is undefined behaviour.

In both calls, sort() winds up reversing the sequence it was given. This is just an accident, an unintended random side effect of the way sort() happens to be implemented on your system. You are likely to get a different result (such as a crash) if you try it with a different compiler.

Upvotes: 4

Related Questions