Taha1506's blog

doubt about c++ sort function
By Taha1506, history, 3 years ago, In English

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.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

Try this:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector<pair<pair<int, int>, int> > summary{ {{1,0},0}, {{0,0},0} };
    sort(summary.begin(), summary.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
            return a.first.second < b.first.second;
        });
    for(auto x:summary)
        cout<<x.first.first<<x.first.second<<x.second<<" ";
}

Output is 100 000.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +23 Vote: I do not like it

      std::sort is not stable. Use std::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.

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

      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.

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

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!

→ Reply