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

Question

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

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没有出现在输入列表中。为什么会这样？

- Aly

8

应该是 return a.second > b.second;。 - jrok

这是您的代码的可读性大大提高的版本（带有修复的谓词）。http://coliru.stacked-crooked.com/a/3f90bd7b88593bbf 这就是您的帖子本应该看起来的样子:/ - sehe

2个回答

3

在C++中，“比较”谓词必须是严格弱序。例如，情况descending_sort(X, X)（两个元素相同）应该总是返回false。

此外，在参考文献中指出：

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

对于descending_sort，这意味着：

return a.second >= b.second;

应该是

return a.second > b.second;

- Pierre Fourgeaud

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- billz · Accepted Answer

您的代码会导致未定义行为，因为 std::sort() 需要一个严格弱序，其中 < 或 > 提供，但 >= 由于违反了反对称性的要求而不提供。

关于 严格弱序，它还包括以下属性：

(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 必须在值上引入严格弱序才能正常工作。

要了解更多关于严格弱序的内容，请阅读更多。