CODEWITHSUNDEEP
c++stl
user389955
user389955

Reputation: 10457

how to sort vector<vector<int>>

I wrote a compare() function to sort vector< vector < int > > and it crashes.

Specifically, if I call sort(u.begin(),u.end()); no crash happens. However if I call sort(u.begin(),u.end(), compare); It crashed, even if compare() simply returns true with no more code. What is wrong with my code? 

bool compare_4sum(vector<int>& a, vector<int>& b){
    return true;
}

void test(){    
    vector<int> x; 
    x.push_back(1);
    x.push_back(2);
    vector<int> x2;
    x2.push_back(2);
    x2.push_back(4);    
    vector<vector<int>> u;    
    u.push_back(x);
    u.push_back(x2);
    sort(u.begin(),u.end(), compare);
}

Upvotes: 0

Views: 196

Answers (2)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

Your comparison function must provide a strict-weak ordering. If it does not, then your call to sort exhibits undefined behavior.

25.4/3 & 4

3) For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i,*j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

4) The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

— comp(a, b) && comp(b, c) implies comp(a, c)
— equiv(a, b) && equiv(b, c) implies equiv(a, c) [ Note: Under these conditions,
  it can be shown that
    — equiv is an equivalence relation
    — comp induces a well-defined relation on the equivalence classes determined
      by equiv
    — The induced relation is a strict total ordering. —end note ]

Upvotes: 6

Yuushi
Yuushi

Reputation: 26040

It likely crashes because a comparison function for sort must follow a strict weak ordering. Your comparison fails on just about all accounts:

For all x, it is not the case that x < x

This will obviously fail.

For all x, y, if x < y then it is not the case that y < x

compare_4sum(x, y) will be true, as will compare_4sum(y, x), hence breaking this.

And so on down the list. You must be very careful when writing predicates for use in std::sort that they do not break this contract, otherwise you're likely to get crashes.

Also, any comparison function should never modify the values it operates on, hence you should always be passing by const &, not &.

Upvotes: 6

Related Questions