C++ 排序 lambda 比较器 EXC_BAD_ACCESS

Question

我遇到了以下代码引发 EXC_BAD_ACCESS 错误的奇怪问题。

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

如果我运行:

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) 做了什么导致了错误？带有数据的完整源代码在这里：https://pastebin.com/r7muQhu7

我的环境：

Apple LLVM version 9.1.0 (clang-902.0.39.2)
Target: x86_64-apple-darwin17.7.0

Answer 1

您的 lambda 不满足排序比较函数的必要条件，即比较函数必须强加 strict weak ordering (although in practice you usually have a total ordering)。

考虑到在你的情况下 {1, true} 小于 {1, true}，不能小于它本身。

这个有效

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

和

一样

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

Answer 2

the following code throws EXC_BAD_ACCESS error [...]

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

@john 的回答以正确的方式解决了这个问题，并且根据 OP 做错了什么给出了很好的解释。我想补充一下为什么可能会抛出 EXC_BAD_ACCESS。 std::sort() 的原因通常是使用 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 实现的，因为您的程序 尝试使用比调用堆栈 上可用的更多 space。在某些平台中，这会转化为 EXC_BAD_ACCESS 信号。

C++ 排序 lambda 比较器 EXC_BAD_ACCESS

C++ sort lambda comparator EXC_BAD_ACCESS

c++

lambda

exc-bad-access

c++11