Краткий ответ

Компаратор для std::sort обязан задавать строгое слабое упорядочение. Если результат сравнения зависит от истории вызовов или нарушает свойства такого упорядочения, программа теряет гарантии корректности: результат сортировки не определён требованиями алгоритма, а поведение может быть неопределённым.

Компаратор должен быть согласованным: для одного и того же состояния данных он не должен противоречиво менять отношение между элементами.

Исторический контекст

STL отделяет алгоритмы от конкретных типов контейнеров и элементов. Благодаря этому один алгоритм сортировки может работать с разными диапазонами, а правило порядка передаётся отдельно в виде компаратора.

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

Постановка проблемы

Для строгого слабого упорядочения должны выполняться, в частности, следующие свойства:

иррефлексивность: элемент не меньше самого себя по компаратору;
асимметричность: если a меньше b, то b не может быть меньше a;
транзитивность: из a меньше b и b меньше c следует, что a меньше c;
эквивалентность элементов, когда ни один из них не меньше другого, также должна быть транзитивной.

Нарушение этих условий может привести к неправильной перестановке элементов, зацикливанию внутренних шагов или другим последствиям, на которые стандарт не даёт гарантий. Отладочная сборка иногда обнаруживает проблему, но успешный запуск отдельного теста не доказывает корректность компаратора.

Подробное решение

Алгоритм не обязан проверять все свойства компаратора. Он предполагает, что сравнение образует согласованную структуру порядка, и использует результаты предыдущих сравнений при выборе опорных элементов и разбиении диапазона.

Строгое слабое упорядочение не требует различать любые два элемента. Например, компаратор может сравнивать только поле priority; элементы с одинаковым приоритетом будут эквивалентны. Это допустимо, если отношение между приоритетами само согласовано.

Корректный пример:

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 3, 2};
    std::sort(values.begin(), values.end(),
              [](int a, int b) { return a < b; });
}

Некорректны, например, компараторы на основе <=, случайного результата, изменяемого глобального состояния или циклического отношения вроде «0 меньше 1, 1 меньше 2, 2 меньше 0». Также опасно сравнивать целые числа через выражение a - b < 0: переполнение знакового типа способно нарушить логику сравнения ещё до работы алгоритма.

Если нужен детерминированный порядок для эквивалентных элементов, можно добавить последовательное сравнение по вторичному ключу. Если же требуется сохранить исходный порядок эквивалентных элементов, следует рассматривать std::stable_sort, но сам компаратор всё равно обязан удовлетворять тому же контракту.

Ситуация из практики

В системе объекты сортировали по времени выполнения задачи. Первоначальный компаратор сравнивал только разность времён: left.time - right.time < 0. На обычных данных он работал, но при значениях около границ типа возникали переполнения и непредсказуемый порядок.

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

Выбранное решение — обычное сравнение left.time < right.time, а при равенстве времени сравнение по уникальному идентификатору. Оно не требует арифметического вычитания, задаёт полный детерминированный порядок и устраняет нестабильные результаты сортировки.

Что кандидаты часто упускают

Обязательно ли компаратору задавать полный порядок без эквивалентных элементов?

Нет. Для std::sort достаточно строгого слабого упорядочения. Два разных объекта могут быть эквивалентны с точки зрения компаратора, если comp(a, b) и comp(b, a) одновременно возвращают false. Полный порядок нужен только тогда, когда его требует логика приложения или он добавляется вторичным ключом.

Почему сравнение через вычитание опаснее прямого сравнения?

Для знаковых целых a - b может выйти за пределы диапазона типа, что приводит к неопределённому поведению ещё на этапе вычисления разности. Выражение a < b не требует арифметической операции и непосредственно проверяет нужное отношение, поэтому является предпочтительным вариантом.

Можно ли компаратору использовать изменяемое внешнее состояние?

Только если это состояние не меняется во время работы алгоритма и результат сравнения остаётся согласованным. Компаратор, который зависит от счётчика вызовов, генератора случайных чисел или изменяемой глобальной переменной, может по-разному сравнить одну и ту же пару элементов. Такой компаратор нарушает контракт алгоритма и не должен использоваться для сортировки.