6

配列「_vec」の値に基づいてインデックスをソートするための単純なコンパレータを実装しようとしています。「無効な < 演算子」という実行時エラー メッセージが表示されます。次のコードの何が問題なのか理解できません。

class Compare{
vector<int>& _vec;
public:
    Compare(vector<int>& vec) : _vec(vec) {}
    bool operator()(size_t i, size_t j){
        if(_vec[i] != _vec[j])
        return _vec[i] < _vec[j];
        else
        return (double)rand()/RAND_MAX < 0.5; 
    }
};

次の関数呼び出しを使用しています。

sort(inds.begin(),inds.end(),Compare(vals));

ここで、inds は 1 から 15 までのインデックス (たとえば) を含む単なる配列であり、vals は長さ 15 の配列で、ソートされたインデックスを計算したい値が含まれています。全体的な目標は、vals の 2 つ (またはそれ以上) のエントリが等しい場合に、並べ替え順序をランダム化することです。何か助けはありますか？

4

2 に答える 2

7

std::sort()は、比較操作が安定していることを期待しています。2 つの項目を比較したときに特定の結果が返された場合、それらの項目が後で再度比較された場合、比較は同じ結果を返す必要があります。ランダムな値を返す場合、必ずしもそれが保持されるとは限りません。

C++03 25.3/4 「並べ替えと関連する操作」は次のように述べています。

equiv(a, b) を !comp(a, b) && !comp(b, a) と定義すると、comp と equiv の両方が推移的な関係であることが要件になります。

  • comp(a, b) && comp(b, c) は comp(a, c) を意味します
  • equiv(a, b) && equiv(b, c) は equiv(a, c) を意味します

[注: これらの条件下では、

  • equiv は同値関係
  • comp は、equiv によって決定される同値クラスに明確に定義された関係を誘導します。
  • 誘導関係は厳密な全順序付けです。

—終わりのメモ]

明確にするために、表 28 は等価関係を定義します。

==は同値関係です。つまり、次のプロパティを満たします。

  • すべての a について、a == a.
  • a == b の場合、b == a.

したがって、あなたのCompare()操作は同等の関係を生み出しません。

データをランダムに失うのではなく、アサーションを取得するのはちょっといいことです。

2 つ (またはそれ以上) のエントリ_vecが等しい場合にソート順をランダム化する問題を解決する 1 つの方法は、それらのインデックスのランダム値を作成し、インデックス => ランダム値または何かのマップでそれらのランダム値を追跡することです。これらのランダムな値を追跡し、推移的で等価なプロパティがCompare()保持されるように使用するようにしてください。

于 2012-09-23T02:40:40.410 に答える
3

std::sort小なり演算子が推移的な関係を提供することを期待しています。つまり、並べ替えA < Bが真であると見なされ、真でB < Cある場合、それも真であることを意味しA < Cます。

あなたの実装では、推移性のルールは成り立ちません。2 つの項目が等しい場合、一方が他方よりも大きいことをランダムにソートに伝えます。これにより、デバッグ アサーションがトリガーされます。

これを修正するには、等しい値に対して false を返します。

于 2012-09-23T02:41:46.393 に答える