3

私が見ている奇妙な動作の再現可能な例を見つけることができましたstd::sort

ペアのリストをソートしようとしていますが、2 番目の要素でソートする必要があります。2 番目の要素のリストは[1 1 1 1 3 1 1 1 1 1 1 3 2 1 1 5 2 1 7 1].

以下は私のコードです：

std::vector<pair<int, double> > pairs;
for (int i = 0; i < 4; i++) {
    pairs.push_back(pair<int, double>(1, 1));
}
pairs.push_back(pair<int, double>(1, 3));
for (int i = 0; i < 6; i++) {
    pairs.push_back(pair<int, double>(1, 1));
}
pairs.push_back(pair<int, double>(1, 3));
pairs.push_back(pair<int, double>(1, 2));
pairs.push_back(pair<int, double>(1, 1));
pairs.push_back(pair<int, double>(1, 1));
pairs.push_back(pair<int, double>(1, 5));
pairs.push_back(pair<int, double>(1, 2));
pairs.push_back(pair<int, double>(1, 1));
pairs.push_back(pair<int, double>(1, 7));
pairs.push_back(pair<int, double>(1, 1));

ソート機能は次のとおりです。

template<typename T>
struct descending_sort {
    bool operator()(pair<T, double> const & a, pair<T, double> const & b) const {
        cout << "sorting (" << a.second << " , " << b.second << ")" << std::endl;
        return a.second >= b.second;
    }
};

descending_sort < int > d = descending_sort<int>();
std::sort(pairs.begin(), pairs.end(), d);

これは正しい結果を生成しますが、各ステップでの sort 関数の出力 (コンソールに出力したもの) を少し詳しく調べると、非常に興味深い出力が得られます。

出力全体はここで見つけることができますが、次のような奇妙な行 (つまり、リンクされたページの 46 行目) があります。

sorting (0 , 1)

しかし、0 は入力リストに表示されません。なぜこれがここにあるのですか？

4

2 に答える 2

16

あなたのコードは、厳密なstd::sort()弱い順序付けを必要とするため、未定義の動作につながります。<>>=

に関してstrict weak orderingは、以下のプロパティも含まれます

(1)非対称

That for operator <: If x < y is true, then y < x is false.
That for a predicate op(): If op(x,y) is true, then op(y,x) is false.

(2)他動詞

演算子 < の場合: x < y が true で y < z が true の場合、x < z は true です。述語 op() の場合: op(x,y) が true で op(y,z) が true の場合、op(x,z) は true です。

(3)反射しない

That for operator <: x < x is always false.
That for a predicate op(): op(x,x) is always false.

(4)等価性の推移性。これは大まかに次のことを意味します。a が b と等価であり、b が c と等価である場合、a は c と等価です。

§ 25.4.4

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

厳密な弱い順序付けの詳細を読むには

于 2013-09-23T11:32:23.680 に答える