std::sort 比较函数导致堆缓冲区溢出

Question

我编写了以下比较函数用于排序：

bool cmp(int a, int b) {
    return a % 2 == 0;
}

让偶数在奇数前面，在较小的测试用例中你会得到 AC，但在较大的用例中会得到堆缓冲区溢出。

但是当我改为：

bool cmp(int a, int b) {
    return a % 2 == 0 && b % 2 == 1;
}

效果完美。

我想知道他们在这个问题上有什么不同。这个问题在leetcode上，链接如下。 https://leetcode.com/problems/sort-array-by-parity/description/

这是我解决这个问题的完整代码

// bool cmp(int a, int b) {
//     return a % 2 == 0;
// }//wrong method

// bool cmp(int a, int b) {
//     return a % 2 == 0 && b % 2 == 1;
// }//AC method
class Solution {
    public:
        vector<int> sortArrayByParity(vector<int>& nums) {
            sort(nums.begin(),nums.end(),cmp);
            return nums;
        }
};

我认为这两个功能都可以满足问题的要求。我想知道为什么会有这样的差异。

Answer 1

您的第一个比较器：

bool cmp(int a, int b) { return a % 2 == 0; }

不遵守使用std::sort

所需的

严格弱排序的要求。

严格弱排序的要求是：

• 它是非自反的：对于所有 x，r(x, x) 为假；
• 它是传递性的：对于所有 a、b 和 c，如果 r(a, b) 和 r(b, c) 都为真，则 r(a, c) 为真；
• 设 e(a, b) 为 !r(a, b) && !r(b, a)，则 e 是传递性的： e(a, b) && e(b, c) 蕴涵 e(a, c) .

但是

cmp(4,4)

会返回

true

，违反了第一个要求（反身性）。

使用这样的比较器的结果是未定义的行为，这意味着任何事情都可能发生（包括堆缓冲区溢出）。

第二个比较器不违反要求，因此可以。