Custom Compare Function for Sorting in C++ STL

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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!

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.

Комментарии (9)

Показать архивные | Написать комментарий?

seduneon

4 года назад, # |

← Rev. 2 →

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

→ Ответить

adipro1167

4 года назад, # ^ |

I tried that also and got the same result.

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?

elliotlarez

3 года назад, # ^ |

-21

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

qwexd

because https://codeforces.net/blog/entry/70237

abhishekpm24

8 месяцев назад, # ^ |

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

Actium

← Rev. 6 →

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:

Geothermal

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.

albjeno

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.

Блог пользователя adipro1167