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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

Алгоритм сортировки может легко зацикливаться, потому что вы говорите, что A

Answer 6

Строгий слабый порядок означает a