C ++ сортировка лямбда-компаратора 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

следующий код выдает ошибку EXC_BAD_ACCESS [...]

Мне интересно, что делает ((a.first == b.first) && a.second), которая вызвала ошибку?

Ответ @Джон решает проблему совершенно правильно и с хорошим объяснением, с точки зрения того, что ФП сделал не так.Я хотел бы добавить, почему конкретно EXC_BAD_ACCESS мог быть брошен.Причина в том, что std::sort() обычно реализуется с использованием Quick Sort , которое обычно пишется рекурсивным способом.Следовательно, тот факт, что вы не предоставили строгий (слабый) порядок, определенно мог привести к тому, что он начал бесконечную рекурсию именно в той точке сравнения, где что-то меньше, чем он сам.то есть сравнение вернет истину независимо от порядка операндов.Эта бесконечная рекурсия является прямой причиной переполнения стека , поскольку ваша программа пытается использовать больше места, чем доступно в стеке вызовов .На некоторых платформах это означает сигнал EXC_BAD_ACCESS.

Answer 2

Ваша лямбда не удовлетворяет условиям, необходимым для функции сравнения сортировки, а именно функция сравнения должна наложить строгий слабый порядок (хотя на практике у вас обычно есть общий порядок ).

Учтите, что в вашем случае {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));