Hi!. In a recent contest I needed to sort a container of form vector<pair<pair<int, int>, int> > and the container only contained not-negative integers I needed two functionality:
1.The vector is sorted by second element of the first element of the outer pair.
2.The pair {{0, 0}, 0} is always at the beginning.
so I used the sort function with comparator as follows:
sort(summary.begin(), summary.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.first.second < b.first.second;
});
Where summary is the vector I want to sort. I got wrong answer in the half of the test cases and I didn't really know why. Then I replaced it with the following code and It magically worked!
sort(summary.begin(), summary.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
if (a.first.second == b.first.second) {
return a < b;
} else {
return a.first.second < b.first.second;
}
});
Any idea on what's going on? I thought it was because of not guranteeing that {{0, 0}, 0} is at first but by trying some cases it was always at the first. The statement of the problem is in persian so I will translate it and put it here as soon as I can if it is not really clear from the sort that where I am wrong.
Try this:
Output is
100 000
.Thanks I see. But how is this possible most of the sorting algorithms are stable aren't they?BTW how did you come up with this counter example?
std::sort
is not stable. Usestd::stable_sort
instead.As far as the counter-example is concerned, you can simply run a stress-test on your own computer. Note that it might have a different
std::sort
implementation, and might give different result since the ordering of elements that compare equal is not defined by the standard, so implementations are free to choose any of them.In my example, initially elements were in wrong order, but comparator tells that they are equal. So even if sorting were stable, output would be the same.
The same thing happened with even me too 12 months back in some contest and from that moment i chose to completely specify me comparator functions like how to compare if first elements of the pairs are equal!