0

我写了一个 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);
}
4

2 回答 2

6

它可能会崩溃，因为 sort 的比较函数必须遵循严格的弱排序。您的比较几乎在所有帐户上都失败了：

对于所有 x，情况并非 x < x

这显然会失败。

对于所有 x, y，如果 x < y 则不是 y < x

compare_4sum(x, y)will be true, as will compare_4sum(y, x), 因此打破这一点。

依此类推。在编写谓词以供使用时必须非常小心，std::sort因为它们不会破坏此合同，否则您可能会崩溃。

此外，任何比较函数都不应该修改它所操作的值，因此您应该始终通过const &，而不是&。

于 2013-08-30T05:17:34.100 回答
6

您的比较函数必须提供严格弱排序。如果没有，那么您对 ​​sort 的调用会表现出未定义的行为。

25.4/3 & 4

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

4) 术语 strict 指的是非自反关系的要求 (!comp(x, x) 对所有 x)，术语 weak 指的是不如全序的要求强，但比 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 ]
于 2013-08-30T05:17:41.080 回答