Свой порядок: Компараторы

sort знает один порядок для чисел, один для строк и один для пар. Настоящие правила редко бывают такими простыми: сначала больше очков, потом меньше игр, потом имя. А у структуры порядка нет вовсе, пока вы его не зададите. Этот урок о том, как объяснить sort, что значит «идёт раньше».

Компаратор: правило в виде функции

В турнире участвовали n игроков. У каждого есть имя, число очков и число сыгранных игр. Выведите рейтинг: сначала больше очков; при равных очках — тот, кто сыграл меньше игр; при равенстве и этого — по алфавиту.

Игрок — структура с тремя полями, а у правила три уровня. Запишем правило как функцию типа bool от двух игроков, отвечающую на один вопрос: должен ли a идти раньше b? Затем передадим эту функцию в sort третьим аргументом — туда, где на прошлом уроке стоял greater<int>():

Для Zara 7 4, Ali 9 5, Timur 7 3, Bek 7 3 программа печатает сначала Ali (9 очков), потом Bek и Timur (по 7 очков и по 3 игры, так что решает имя), потом Zara (7 очков, 4 игры). Такая функция называется компаратором, и у любого компаратора одна и та же форма — лестница:

Правила, которым обязан подчиняться компаратор

sort полностью доверяет компаратору, и компаратор, нарушающий правила, заставляет sort выдать мусор или даже упасть. Два правила покрывают почти всё:

• Строгость. cmp(x, x) должно быть false: элемент не идёт раньше самого себя. Поэтому сравнивайте через < или >, никогда через <= или >=. Лестница выше делает это сама: при равных ключах сравнение спускается ниже, и последняя строка возвращает false для равных элементов.
• Согласованность. Если a раньше b, а b раньше c, то a должен быть раньше c. «Камень, ножницы, бумага» это правило нарушает: камень бьёт ножницы, ножницы бьют бумагу, а бумага — камень. Если правило «победитель идёт первым», три предмета ходят по кругу, а sort не умеет сортировать круг.

Компаратор никогда не меняет элементы и не читает ничего, кроме двух элементов, которые ему дали.

Лямбда: компаратор, написанный на месте

Для короткого правила отдельная функция — слишком много писанины. C++ позволяет написать функцию прямо внутри вызова: [](const string &a, const string &b) { … } — это функция без имени, . Всё остальное то же самое: на вход две константные ссылки, на выход .