C++ sort lambda comparator EXC_BAD_ACCESS

Question

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

Answer 1

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));