C++ sort lambda comparator EXC_BAD_ACCESS

user_1475320 0
Viewed 394

I experienced this weird issue that the following code throws EXC_BAD_ACCESS error.

using T = pair<int, bool>;
sort(vp.begin(), vp.end(), [](const T& a, const T& b) {
    return (a.first < b.first) || ((a.first == b.first) && a.second);
});

If I run:

using T = pair<int, bool>;
sort(vp.begin(), vp.end(), [](const T& a, const T& b) {
    return (a.first < b.first);
});

It works. If I reduce the data size, it works too. I am curious what does ((a.first == b.first) && a.second) do that caused the error? Complete source code with data is here: https://pastebin.com/r7muQhu7

My environment:

Apple LLVM version 9.1.0 (clang-902.0.39.2)
Target: x86_64-apple-darwin17.7.0
exc-bad-access c++11 lambda c++
2 Answers

Your lambda doesn't satisfy the conditions necessary for a sort comparison function, namely a comparison function must impose a strict weak ordering (although in practice you usually have a total ordering).

Consider that in your case {1, true} is less than {1, true}, something can't be less than itself.

This works

return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second));

as does

return (a.first < b.first) || ((a.first == b.first) && (a.second > b.second));
user_8820030

the following code throws EXC_BAD_ACCESS error [...]

I am curious what does ((a.first == b.first) && a.second) do that caused the error?

The answer by @john solves the issue exactly the right way, and with good explanation, in terms of what the OP did wrong. Id like to add why specifically a EXC_BAD_ACCESS might have been thrown. The reason in that std::sort() is usually implemented using Quick Sort, which is typically written in a recursive manner. Hence, the fact that you didn't provide the strict (weak) ordering, could have definitely caused it to enter an endless recursion exactly at that point of comparison where something is less than itself. i.e. the comparison will return true no matter the order of the operands. This endless recursion is the direct cause of a stack overflow, as your program attempts to use more space than is available on the call stack. In certain platforms this translates to a EXC_BAD_ACCESS signal.

user_27541730
Related