c++ - 如何排序 vector>

Question

我写了一个 compare() 函数来排序 vector< vector < int > >它崩溃了。

具体来说，如果我调用 sort(u.begin(),u.end());没有崩溃发生。但是，如果我调用 sort(u.begin(),u.end(), compare);它崩溃了，即使compare()简单地返回 true没有更多的代码。我的代码有什么问题？

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

Answer 1

您的比较函数必须提供 strict-weak ordering .如果没有，那么您对 ​​sort 的调用将表现出未定义的行为。

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 ]