CODEWITHSUNDEEP
c++sortingcomparestd
LouieK
LouieK

Reputation: 9

std::sort compare function caueses a heap-buffer-overflow

I wrote the following compare function for sorting:

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

Let the even number be in front of the odd number, and you will get AC in a small test case but a heap-buffer-overflow in a larger case.

But when I changed to:

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

It works perfectly.

I wonder what's different between them in this problem. This problem is in leetcode, and the link is following. https://leetcode.com/problems/sort-array-by-parity/description/

and this is my full code of this problem

// 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;
        }
};

I think both functions can meet the requirements of the question. I want to know why there is such a difference.

Upvotes: 0

Views: 99

Answers (1)

wohlstad
wohlstad

Reputation: 28774

Your first comparator:

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

does not respect the requirements of strict weak ordering which is required for using std::sort.

The requirements for strict weak ordering are:

  • it is irreflexive: for all x, r(x, x) is false;
  • it is transitive: for all a, b and c, if r(a, b) and r(b, c) are both true then r(a, c) is true;
  • let e(a, b) be !r(a, b) && !r(b, a), then e is transitive: e(a, b) && e(b, c) implies e(a, c).

But cmp(x,x) will return true for any even number x (e.g.: cmp(4,4)), violating the first requirement (irreflexivity).

The result of using such a comparator is undefined behavior, which mean anything can happen (heap-buffer-overflow included).

The second comparator does not violate the requirements and is therefore OK.

Upvotes: 4

Related Questions