如果比较函数不像运算符 <? 那样，为什么 std::sort 会崩溃？

Question

以下程序是使用VC++ 2012编译的。

#include <algorithm>

struct A
{
    A()
        : a()
    {}

    bool operator <(const A& other) const
    {
        return a <= other.a;
    }

    int a;
};

int main()
{
    A coll[8];
    std::sort(&coll[0], &coll[8]); // Crash!!!
}

如果我将return a <= other.a;更改为return a < other.a;，那么程序将按预期运行，不会出现异常。

为什么？

- xmllmx

---

std::sort 的比较器需要严格弱序，而 <= 是不符合该要求的。 - WhozCraig

@GManNickG，不，它不会。就确定性而言，是不行的。 - László Papp

是的，它会进行值初始化a()（这就是a()的意思），对于int类型来说，这意味着0。 - GManNickG

@LaszloPapp: https://dev59.com/_2Yq5IYBdhLWcg3wuiwz初始化列表中的默认值 - GManNickG

请用 coll + 8 替换未定义的行为 &coll[8]。 - user2249683

Answer 1

std::sort需要一个符合严格弱序规则的排序器，关于该规则的解释可以在这里找到。

因此，你的比较器如果是a == b时就返回a < b，那么它不遵循严格弱序规则，可能会导致算法进入无限循环而崩溃。

- xorguy

---

这句话说明了std::sort的比较器要求，建议使用std::sort(std::begin(coll), std::end(coll));进行排序，如果你的编译器符合C++11标准（OPs的VS2012符合），当你改变数组的维度或使用其他标准容器时会感到庆幸。 - WhozCraig

进入无限循环应该只会导致程序卡住，但实际上它会导致核心转储。为什么？ - btilly

@btilly 我认为是因为 std::sort 使用递归算法，如果出现无限循环，将会导致堆栈溢出。 - xorguy

你需要具体了解它检查的内容，但标准排序例程旨在非常快速地运行，因此它们不会检查每个操作以查看是否正确，而是依赖于它。如果您的比较返回不可能的结果，那么不可能的事情将会发生——比如说它得到了某些比较的结果，并将其用作查找位置的索引，只是它“知道”哪些值是可能的，并且“知道”所得到的引用将在有效存储器中，因此它只需获取它。砰——有幸的话，会出现SIGSEGV错误。如果运气不好，它将悄无声息地破坏您的数据。 - jthill

Answer 2

xorguy的答案非常好。

我只想引用一下标准：

25.4 排序和相关操作 [alg.sorting]

为了使除25.4.3以外的算法正常工作，comp必须对值施加严格弱序关系。

术语“严格”指的是不可反身关系的要求（对于所有x，!comp（x，x）），而术语“弱”则指的是要求不及总序关系那么强，但比偏序关系强。

所以xorguy解释得很好：你的comp函数在a == b时说a<b，这不符合严格弱序关系规则...

- Pierre Fourgeaud

Answer 3

你的代码问题在于访问了无效的内存。代码

coll[8]

尝试访问最后一个数组元素之后的元素（最后一个元素索引为7）。 我建议使用std::array而不是普通的C数组。

std::array<A, 8> a;

// fill it somehow

std::sort(a.begin(), a.end());

- Khabarov Boris