adipro1167's blog

Custom Compare Function for Sorting in C++ STL
By adipro1167, history, 5 years ago, In English

Hello Codeforces! In the contest, Codeforces Round #648, in B problem- Trouble Sort, I thought of using the Custom Compare Function, though later I realized it wasn't required here. But a general problem that I have faced in Custom Compare Function is that I have never understood its working. Sometimes, I make my own Custom Functions and they work but how- I don't understand. I read about it on Sort()-CPP Reference and Sort(): GeeksForGeeks but I did not understand its working. I wrote the following code: 

#define lpr pair<long long int,long long int>
#define S second
#define F first
#define ll long long int
bool comparefn(lpr a, lpr b)
{
    if(a.S!=b.S)
    return a.F<=b.F;
    return false;
}

This is my custom compare function and I used it as:

vector<lpr> a;
sort(a.begin(),a.end(),comparefn)

It passed the first test case successfully but failed in the second one. On debugging I found that it fails for the following case:

5 1 5
0 0 1

Output: No But for the case:

5 5 1
0 1 0

Output: Yes. It works correctly.

Please explain me a dry run of this test case with the custom compare function which I have made. It would be of great help. Thanks in Advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You should use first_value < second_value instead of first_value <= second_value in your compare function.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried that also and got the same result.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean

      bool comparefn(lpr a, lpr b)
{
    if(a.S!=b.S)
    return a.F<b.F; // instead of <=
    return false;
}

      Have you tried it?

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Why you need to do that? I figured out my code was not functioning as it should by using a <= instead of <?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      because https://mirror.codeforces.com/blog/entry/70237

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot qwexd. I tried to debug on my own but could not find mistake for very long. Finally found the mistake after reading this blog. For other people: If you use custom comparator for sorting, don't use <= operator. Instead use < operator. Ex. 

        // correct way
auto comp=[&](int a,int b){
        return a<b;
    };

// leads to all kinds of errors 
auto comp=[&](int a,int b){
        return a<=b;
    };
        → Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it +3 Vote: I do not like it

You need stateful comparator to use STL sort for this problem, your comparefn() cannot be used here.

Let us consider the following input: [3,0 2,1 1,1]

STL implementations differ, but let us assume std::sort() is dispatched to insertion_sort() if the number of elements to be sorted is less than 10 (our case). So we have iterations like this:

1: [3,0]
2: is 2,1 lt 3,0? yes, so swap elements -> [2,1 3,0]
3.1: is 1,1 lt 3,0? yes, so swap elements -> [2,1 1,1 3,0]
3.2: is 1,1 lt 2,1? no (second parts are equal, and comparefn() returns false in this case) so elements are not swapped and data are not sorted as a result.
→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The problem is that the order of the swaps you want to perform may not be the same as the order in which the STL sort function makes its comparisons. The STL sort is one way to sort an array, but it doesn’t perform the only set of swaps that could potentially sort the array. When we can’t necessarily perform any swap we want, we need to verify that all sorting functions fail, rather than just one of them.

In general, going about this problem with built-in sorting cautions just isn’t the right approach. Failing to sort the array using one method of sorting tells you nothing about whether there’s some other way to perform the sorting.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Your comparefn isn't a compare function since it does not fulfil the requirements of the Compare concept, namely that of transitivity. Thus sort can not work with it.

→ Reply