Я собираюсь ответить на свой вопрос, но большое спасибо Полу Маккензи за помощь в обсуждении и ответ Виктора Истомина.
Оказывается, сортировка не работает так, как я думал. Он ожидает, что строго-слабый порядок , что означает, что a > b
и b > a
не могут быть одновременно истинными, в противном случае поведение не определено . Кроме того, его способ определить, равны ли 2 элемента, использует !(a < b) && !(b > a)
, поскольку он использует только оператор <
вместо оператора ==
.
Ошибка в моем коде состоит в том, что я всегда возвращаю false в этом случае, так что выражение !(a < b) && !(b > a)
будет истинным, и sort считает их равными, таким образом не меняя их местами.
Правильное решение, как указывает PaulMckenzie, использует stable_partiion
(или partition
, если относительный порядок не требуется). Принцип состоит в том, чтобы использовать сортировку только тогда, когда у нас есть четкое правило сравнения элементов, если мы просто хотим сгруппировать одни и те же элементы, partition
- это хорошо.
Кажется, у меня были некоторые ложные заблуждения относительно функции сортировки, спасибо за указание.
----------------- обновление ----------------
Калет указывает в комментарии, что строгий-слабый порядок не применяется, но его поведение будет неопределенным в случае нарушения. Обновлено мое описание этой части. Спасибо.