3

我设法找到了我所看到的奇怪行为的可重现示例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);

这会产生正确的结果,但是当我仔细检查每一步的排序函数的输出(我打印到控制台的内容)时,我会得到一些非常有趣的输出。

整个输出可以在这里找到,但是有一些奇怪的行(即链接页面中的第 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 为真且 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

对于所有采用比较的算法,都有一个使用 operator< 的版本。也就是说,1comp(*i,*j) != false1 默认为 *i < *j != false。为了使 25.4.3 中描述的算法以外的算法正常工作,comp 必须对值进行严格的弱排序。

阅读有关严格弱排序的更多信息

于 2013-09-23T11:32:23.680 回答
3

在 C++ 中,“比较”谓词必须是严格的弱排序。例如,案例descending_sort( X, X )(两对相同)应始终返回false.

此外,在此参考文献中,据说:

comp - 如果第一个参数小于第二个参数,则返回 ​true 的比较函数。

对你来说,这意味着descending_sort

return a.second >= b.second;

应该

return a.second > b.second;
于 2013-09-23T11:36:15.713 回答