如果比较功能不像运算符<那样，为什么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;则程序将正常运行，没有例外。

为什么？

Answer 1

std::sort需要其满足分拣机严格弱排序规则，这是解释 在这里因此，您的比较器说，a < b当a == b不遵循严格的弱排序规则时，该算法可能会崩溃，因为它将进入无限循环。

Answer 2

xorguy的答案非常好。我只是从标准中添加一些报价：25.4排序及相关操作[alg.sorting]为了使25.4.3中描述的算法无法正常工作，comp必须在值上引入严格的弱排序。术语“ 严格”是指对非自反关系的要求（！comp（x，x）对于所有x），而术语“ 弱于”的要求不如总订购的要求强，但要强于部分订购的要求。 。所以xorguy很好地解释了这一点：您的comp函数说，a < b当a == b哪个不遵循严格的弱排序规则时...

Answer 3

您必须详细了解它要检查的内容，但是标准的排序例程旨在非常非常快地运行，因此它们不必检查您所做的任何事情就可以了，而只是依靠它。如果您的比较返回不可能的结果，那么将不可能发生的事情-说它得到了一些比较的结果，并将其用作查看位置的索引，只有它“知道”可能的值并“知道”结果引用将存储在有效存储中，因此只需将其提取即可。Kaboom：SIGSEGV运气不错。如果运气不好，它将无声地管理您的数据