如何对vector <vector <int >>进行排序

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

它可能会崩溃,因为sort的比较函数必须遵循严格的弱排序.几乎所有帐户的比较都失败了:

对于所有x,不是x <x的情况

这显然会失败.

对于所有x,y,如果x <y则不是y <x的情况

compare_4sum(x, y)会true,因为意志compare_4sum(y, x),从而打破这一点.

等等列表.在编写谓词以供使用时std::sort,您必须非常小心,因为它们不会违反此合同,否则您可能会崩溃.

此外,任何比较函数都不应该修改它所操作的值,因此你应该总是路过const &,而不是&.

Answer 2

您的比较函数必须提供严格弱的排序.如果没有,那么您对sort的调用会显示未定义的行为.

25.4/3和4

3)对于所有采用比较的算法,有一个使用operator <的版本.也就是说,comp(*i,*j)!= false默认为*i <*j!= false.对于25.4.3中描述的算法之外的算法无法正常工作,comp必须对值进行严格的弱排序.

4)术语严格是指对所有x的反自由关系的要求(!comp(x,x)),对于要求的要求不弱于总排序的要求,但强于a的要求偏序.如果我们将equiv(a,b)定义为!comp(a,b)&&!comp(b,a),则要求comp和equiv都是传递关系:

— 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 ]