C++は、ソートの反復が、時には間違った値に

Question

tour_indexes.clear(); 
for (int i=0; i<num_of_cities; i++) 
{ 
    tour_indexes.push_back(i); 
} 

mt19937 gen(random_engine()); 
uniform_real_distribution<> dis(0, 1); 

// Sort indexes based on comparing values in tour. Choose at random if equal 
sort(tour_indexes.begin(), tour_indexes.end(), 
    [&tour, &dis, &gen](int &i1, int &i2) 
{ 
    if (tour[i1] == tour[i2]) 
    { 
     return dis(gen) < 0.5; 
    } 
    return tour[i1] < tour[i2]; 
}); 

を与えるこれは私にtour[i1] == tour[i2]にセグメンテーションフォルトを与え、そしてデバッグするとき、私はi2は時々（一見非決定論的）それがあるべきよりも道大きいので、それがあることがわかります。 tour_indexesがf.ex 0-20であるときには、F.ex 403163787（それは変化する）（tour_indexesにはi2が含まれていないというエラー時に2回チェックした）。

これはすべて、メンバ変数tour_indexesを含むクラスのメンバ関数で発生します。クラスオブジェクトは、関連する場合はshared_ptrにあります。何が問題なのでしょうか？ありがとう。

Answer 1

コンパレータは厳密な弱い順序を提供しません。具体的には、tour[i1] == tour[i2]の場合、trueまたはfalseを返す確率は50/50です。と答えが安定しない（必須）。

比較関数が厳密な弱い順序付けを提供しない場合、その動作は定義されておらず、seg-faultは1つのもっともらしい動作です。

私は使用をお勧めしますreturn i1 < i2;これは安定した方法でタイを破るでしょう。

また、ネクタイを一切壊す必要はありません。ただ、

[&tour](int i1, int i2) 
{ 
    return tour[i1] < tour[i2]; 
} 

std::sort弱い順序にはかなり満足ですを使用します。 cmp(i1,i2)とcmp(i2,i1)の両方がfalseを返す可能性があります。対処できないのは、両方とも真（同じ引数を持つ2つの呼び出しがの値が異なるの値を返します）です。

Answer 2

比較演算子のランダム化を削除します。おそらく、要素が等しい場合、i1 < i2とi2 < i1の両方が真である可能性があるため、並べ替えアルゴリズムが失敗する可能性があります。

sortは、equal要素とstable_sortが配列内の等しい要素の確定的な順序を与える場合、既にランダムな順序を与えています。