doubt about c++ sort function

Revision en1, by Taha1506, 2021-07-16 17:22:16

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Taha1506 2021-07-16 17:22:16 1368 Initial revision (published)