C++ std :: vector std :: sort бесконечный цикл

Question

Я столкнулся с проблемой всякий раз, когда пытался сортировать вектор объектов, что приводило к бесконечному циклу. Я использую пользовательскую функцию сравнения, которую я передал функции сортировки.

Я смог исправить проблему, вернув false, когда два объекта были равны вместо true, но я не совсем понял решение. Я думаю, это потому, что моя функция сравнения нарушала это правило, как указано на cplusplus.com:

Сравнение функционального объекта, который, принимает два значения одного и того же типа , чем те, которые содержатся в диапазоне, возвращает истину, если первый аргумент предшествует второму аргументу в конкретным строгим слабым порядком его определяет и false в противном случае.

Может ли кто-нибудь предоставить более подробное объяснение?

Answer 1

Правильный ответ, как указывали другие, заключается в том, чтобы узнать, что такое «строгий слабый порядок». В частности, если значение comp(x,y) истинно, то comp(y,x) должно быть ложным. (Обратите внимание, что это означает, что comp(x,x) неверно.)

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

Если вам интересно, что на самом деле пошло не так, то в вашей библиотеке sort, вероятно, используется внутренняя утилита quicksort. Quicksort работает путем многократного поиска пары элементов «вне порядка» в последовательности и их замены.Если ваше сравнение сообщает алгоритму, что a, b «не соответствует порядку», и он также сообщает алгоритму, что b, a «не соответствует порядку», тогда алгоритм может сворачивать их снова и снова навсегда.

Answer 2

Если вы ищете подробное объяснение того, что «строгий слабый порядок» есть, вот некоторые хорошие материал для чтения: Order I Say!

Если вы ищете помощь фиксируя свой функтор сравнения, вам необходимо на самом деле опубликовать его.

Answer 3

Strict weak ordering означает a < b == true, и когда вы возвращаете true для равенства, его значение равно < = b == true. Это требование необходимо для оптимальности для разных алгоритмов сортировки.

Answer 4

Если изделия одинаковые, то одни не идут перед другим. В документации было совершенно ясно, что в этом случае вы должны вернуть false.

Answer 5

Алгоритм сортировки может легко зацикливаться, потому что вы говорите, что A < B И B < A, когда они равны. Таким образом, алгоритм может бесконечно пытаться поменять элементы A и B, пытаясь получить их в правильном порядке.

Answer 6

Фактическое правило указано в стандарте C++, в 25.3[lib.alg.sorting]/2

Сравнить используется в качестве функции объекта, который возвращает true, если первый аргумент меньше второго, и false в противном случае.

Случай, когда аргументы равны, подпадает под «в противном случае».