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)になるのでtrue、compare_4sum(y, x)これを壊します。

などなど。使用する述語を記述するときはstd::sort、この契約を破らないように十分注意する必要があります。そうしないと、クラッシュする可能性があります。

また、比較関数は、操作対象の値を決して変更してはならないため、常にconst &ではなくを渡す必要があります&。

于 2013-08-30T05:17:34.100 に答える
6

比較関数は、strict-weak 順序付けを提供する必要があります。そうでない場合、 sort の呼び出しは未定義の動作を示します。

25.4/3 & 4

3) Compare を使用するすべてのアルゴリズムには、代わりに operator< を使用するバージョンがあります。つまり、comp(*i,*j) != false のデフォルトは *i < *j != false です。25.4.3 で説明されているもの以外のアルゴリズムが正しく機能するためには、comp は値に対して厳密で弱い順序付けを行う必要があります。

4) 厳密という用語は、非反射的な関係 (すべての x に対して!comp(x, x)) の要件を指し、用語は、全順序付けの要件ほど強くないが、完全な順序付けの要件よりも強い要件に弱いことを指します。部分的な順序。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 に答える