std :: sort给出了非常奇怪的结果

Question

我设法找到了一个可重现的例子,说明了我所看到的奇怪行为 std::sort

我试图对一对对列表进行排序,它应该在第二个元素上排序.第二个元素的列表是[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没有出现在输入列表中.这是为什么？

Answer 1

您的代码会导致不确定的行为,因为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为真且y <z为真,则x <z为真.对于谓词op():如果op(x,y)为真且op(y,z)为真,则op(x,z)为真.

(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必须对值进行严格的弱排序.

阅读更多关于严格弱序的说明