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

Проекция преобразует каждый элемент диапазона в значение, по которому затем выполняется сравнение. Поэтому std::ranges::sort может сортировать объекты по полю или вычисляемому ключу без написания компаратора, сравнивающего сами объекты.

Проекция не меняет элементы и не делает неподходящий контейнер сортируемым: алгоритму по-прежнему требуются итераторы произвольного доступа, например у std::vector.

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

Классические алгоритмы STL обычно требуют вручную передавать компаратор. При сортировке объектов по полю такой компаратор должен извлекать ключ из обоих аргументов, что создаёт повторяющийся шаблонный код.

В C++20 ranges-алгоритмы получили отдельный параметр проекции. Это позволило отделить извлечение ключа от правила сравнения и одновременно добавить ограничения типов, проверяемые на этапе компиляции.

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

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

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

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

std::ranges::sort принимает компаратор и проекцию. Концептуально для сравнения двух элементов сначала вычисляются proj(element1) и proj(element2), после чего к полученным значениям применяется компаратор.

Компаратор по умолчанию сравнивает спроецированные значения через std::ranges::less. Проекцией может быть указатель на поле, вызываемый объект или функция, возвращающая вычисляемый ключ.

#include <algorithm>
#include <string>
#include <vector>

struct Record {
    std::string name;
    int score;
};

int main() {
    std::vector<Record> records{{"A", 30}, {"B", 10}, {"C", 20}};
    std::ranges::sort(records, {}, &Record::score);
}

В этом примере сравниваются значения score, а сами элементы Record переставляются в контейнере. Сложность сортировки остаётся O(n log n) в среднем и зависит от требований и гарантий конкретного алгоритма; проекция не превращает сортировку в линейную.

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

Для дорогих вычислений возможна схема decorate-sort-undecorate: заранее сформировать пары «ключ и элемент», отсортировать их по сохранённому ключу, затем получить исходные элементы. Это уменьшает повторные вычисления, но требует дополнительной памяти и отдельной логики восстановления результата.

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

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

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

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

Заменяет ли проекция компаратор полностью?

Нет. Проекция отвечает за преобразование элемента в ключ, а компаратор определяет порядок ключей. Можно передать собственный компаратор для спроецированных значений, например для обратной сортировки или специального порядка эквивалентных ключей.
Кэширует ли std::ranges::sort результат проекции?

Нет такой общей гарантии. Нельзя рассчитывать, что один и тот же ключ будет вычислен единожды для каждого элемента. Для дорогих проекций кэширование нужно реализовать отдельно, принимая расходы на дополнительную память и усложнение кода.
Можно ли проекцией отсортировать std::list?

Нет. Проекция решает только вопрос получения ключа, но не меняет категорию итераторов. std::ranges::sort требует диапазон с итераторами произвольного доступа, поэтому для std::list следует использовать его собственный метод sort, передав компаратор, либо предварительно выбрать другой контейнер.