std :: sort给出非常奇怪的结果 [英] std::sort giving very strange results

问题描述

我设法找到一个可重现的例子，我看到的 std :: sort

I have managed to find a reproducible example of the strange behaviour I am seeing with std::sort

我试图排序对的列表，它应该在第二个元素上排序。第二个元素的列表是 [1 1 1 1 3 1 1 1 1 1 1 3 2 1 1 5 2 1 7 1] 。

I am trying to sort a list of pairs, where it should be sorted on the second element. The list of the second elements is [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);

这会产生正确的结果，但是当我仔细检查每一个排序函数的输出步骤（我打印到控制台）我得到一些非常有趣的输出。

This produces the correct result, but when I examine a bit closely the output of the sort function at each step (what I print to console) I get some very interesting output.

整个输出可以找到这里，但有一些奇怪的行（即链接页面中的第46行）：

The whole output can be found here but there are some strange lines (i.e. line 46 in linked page) which read:

sorting (0 , 1)

但输入列表中不显示0。为什么是这里？

But 0 does not appear in the input list. Why is this here?

推荐答案

您的代码导致未定义的行为，因为 std :: sort 需要严格的弱排序，< 或> 提供， c $ c>> = 不提供，因为违反反对称的要求。

Your code leads to undefined behavior, because std::sort() requires a strict weak ordering, which < or > provides, but >= does not provide because it violates the requirement to be antisymmetric.

code> strict weak ordering ，还包括以下属性

Regarding strict weak ordering, it also include below properties

（1）反对称 >

(1) antisymmetric

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为真，y < z为真，则x < z是真的。
对于谓词op（）：如果op（x，y）为true，op（y，z）为true，则op（x，z）
为真。

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

（3）无反应

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

（4）等效传递性等价于b，b等于c，则a等于c。

(4) transitivity of equivalence, which means roughly: If a is equivalent to b and b is equivalent to c, then a is equivalent to c.

§25.4.4

对于所有采用比较的算法，使用运算符&代替。也就是说，1comp（* i，* j）！= false1默认为* i < * j！= false。 对于25.4.3中描述的算法以外的其他算法，comp必须对值进行严格的弱排序。

要详细了解严格弱排序

这篇关于std :: sort给出非常奇怪的结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！