Использование std::sort в C++: компараторы и примеры

Введение

Сортировка — одна из самых частых операций в программировании. В стандартной библиотеке C++ для неё есть функция std::sort из заголовка <algorithm>. Она работает быстро, подходит для массивов, векторов и других контейнеров с произвольным доступом и легко настраивается под любой порядок. В статье разберём использование std::sort на примерах: сортировку по возрастанию и убыванию, собственные компараторы, сортировку структур, а также родственные алгоритмы stable_sort, partial_sort и nth_element.

Базовое использование std::sort

Функция принимает два итератора: на начало и на конец сортируемого диапазона. По умолчанию элементы упорядочиваются по возрастанию с помощью оператора <:

#include <algorithm>
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers = {5, 2, 9, 1, 7};
    std::sort(numbers.begin(), numbers.end());

    for (int n : numbers)
        std::cout << n << ' ';   // 1 2 5 7 9
}

Так же сортируется обычный массив C: std::sort(arr, arr + size), или с помощью std::begin(arr) и std::end(arr).

Сортировка по убыванию

Третьим аргументом передаётся компаратор — функция, которая возвращает true, если первый элемент должен стоять раньше второго. Для обратного порядка подойдёт готовый объект std::greater или лямбда:

#include <functional>

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

// то же самое с лямбдой
std::sort(numbers.begin(), numbers.end(),
          [](int a, int b) { return a > b; });

Сортировка структур

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

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {
    {"Иван", 30}, {"Анна", 25}, {"Пётр", 35}
};

std::sort(people.begin(), people.end(),
          [](const Person &a, const Person &b) {
              return a.age < b.age;
          });

Если нужно сортировать по нескольким полям, удобно сравнивать кортежи через std::tie. Например, сначала по возрасту, а при равенстве — по имени:

#include <tuple>

std::sort(people.begin(), people.end(),
          [](const Person &a, const Person &b) {
              return std::tie(a.age, a.name) < std::tie(b.age, b.name);
          });

Ещё один вариант — определить для структуры operator<. Тогда std::sort можно вызывать без третьего аргумента.

Требования к компаратору

Компаратор должен задавать так называемый строгий слабый порядок. На практике это значит:

для равных элементов он возвращает false, поэтому используйте < или >, но не <=;
результат не должен меняться между вызовами;
если a раньше b и b раньше c, то a раньше c.

Нарушение этих правил приводит к неопределённому поведению. Программа может отсортировать данные неправильно или даже упасть.

Сложность и ограничения

Начиная с C++11, std::sort гарантирует сложность O(n log n) в худшем случае. Внутри обычно используется introsort — сочетание быстрой сортировки, пирамидальной сортировки и сортировки вставками. Алгоритм требует итераторов произвольного доступа. Поэтому он работает с std::vector, std::array, std::deque и массивами, но не с std::list. У списка есть собственный метод list.sort().

std::sort не стабилен: элементы с одинаковыми ключами могут поменяться местами относительно исходного порядка.

Родственные алгоритмы

std::stable_sort — сохраняет исходный порядок равных элементов. Нужен, например, при последовательной сортировке таблицы по нескольким столбцам.
std::partial_sort — сортирует только первые N элементов. Удобно, когда нужен топ-10 из миллиона записей.
std::nth_element — ставит на своё место только один элемент, например медиану, за линейное время в среднем.
std::is_sorted — проверяет, отсортирован ли диапазон.

// Три самых больших числа
std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(),
                  std::greater<int>());

// Медиана
auto mid = numbers.begin() + numbers.size() / 2;
std::nth_element(numbers.begin(), mid, numbers.end());
int median = *mid;

std::ranges::sort в C++20

В C++20 появилась версия из пространства имён std::ranges. Ей можно передать контейнер целиком и указать проекцию — поле, по которому идёт сравнение:

std::ranges::sort(numbers);
std::ranges::sort(people, {}, &Person::age);   // сортировка по полю age

Заключение

std::sort — основной инструмент сортировки в C++. Для простых случаев достаточно двух итераторов, для особого порядка — компаратора или лямбды. Следите за тем, чтобы компаратор задавал строгий порядок, а если важен порядок равных элементов, выбирайте std::stable_sort. О том, как сортировать контейнеры Qt и чем заменить устаревший qSort, читайте в статьях std::sort vs qSort и сортировка QList.

Использование std::sort в C++