1. Введение
Сортировка — это не только про «красивый список по алфавиту». Обычно сортировка появляется в приложениях как способ сделать данные удобными для пользователя или удобными для дальнейшей логики. Например, в списке задач хочется видеть сначала важное, потом неважное, или сначала невыполненное, потом выполненное. В интернет‑магазине — сначала подешевле. В таблице студентов — по фамилии.
Наивная мысль новичка: «Да я сейчас двумя вложенными циклами всё переставлю». И это правда можно сделать. Но проблема в том, что самодельная сортировка быстро превращается в гнездо ошибок: где-то перепутали границы, где-то не так поменяли местами, где-то сортировка “почти работает”. А стандартная библиотека уже содержит очень оптимизированные реализации, и наша задача — научиться ими пользоваться.
Кстати, сортировка — это как уборка на столе. Можно по одному листочку перекладывать туда‑сюда, пока не станет красиво. А можно сказать: «Разложи по папкам по правилам». std::sort — это как раз «разложи по правилам».
2. std::sort: минимальный рабочий вызов
С технической точки зрения std::sort — это алгоритм из заголовка <algorithm>, который переставляет элементы внутри заданного диапазона. То есть сортировка происходит “на месте”: вы отдаёте вектор, и после вызова std::sort элементы вектора меняют порядок. Это важно держать в голове: если вы где-то запомнили индекс «особого элемента», после сортировки этот индекс, скорее всего, будет указывать вообще не туда.
У std::sort есть форма «по умолчанию»: сортировать по возрастанию с использованием оператора <. На практике это значит: числа будут по возрастанию, строки — по алфавиту (лексикографически), а пользовательские типы — только если у них определён корректный < (но мы сейчас туда не полезем).
Минимальный пример:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{5, 1, 4, 2};
std::sort(v.begin(), v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 1 2 4 5
}
Здесь важно увидеть привычный паттерн «алгоритм + диапазон»: мы не говорим “сортируй вектор”, мы говорим “сортируй элементы от begin() до end()”.
И ещё одна практическая деталь: std::sort требует, чтобы итераторы были «быстрыми» (по сути, чтобы можно было эффективно прыгать по индексам). Поэтому на std::vector и std::array сортировка работает идеально, а на некоторых других контейнерах — иначе (но это уже не тема сегодняшней лекции). В стандарте и связанных обсуждениях итераторов постоянно подчёркивается важность корректных требований к random access итераторам.
3. Компаратор: как задать порядок сортировки
Как только вы хотите сортировать «не как обычно», появляется второе лицо этой лекции — компаратор.
Компаратор — это функция, которая отвечает на вопрос: «Должен ли a идти раньше b?»
То есть компаратор — это функция вида:
bool comp(const T& a, const T& b);
Если comp(a, b) возвращает true, это означает: «a должно стоять перед b в отсортированном порядке».
Почти все ошибки новичков начинаются тут, потому что хочется написать что-то вроде «верни a <= b». Но у компаратора немного другой контракт: он должен задавать строгий порядок, и в типичном случае это выражается через < или > (но не через <=/>=).
Посмотрим на сортировку по убыванию чисел. Сделаем компаратор отдельной функцией (так сейчас лучше для читаемости, чем пытаться “встроить” условие прямо в вызов):
#include <algorithm>
#include <iostream>
#include <vector>
bool greater_int(int a, int b) {
return a > b; // a раньше b, если a больше b
}
int main() {
std::vector<int> v{5, 1, 4, 2};
std::sort(v.begin(), v.end(), greater_int);
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 5 4 2 1
}
Обратите внимание на “чтение” компаратора: return a > b означает «большее число должно стоять раньше». И да, это немного ломает мозг в начале — но потом становится очень удобным: вы буквально пишете правило порядка.
Небольшая табличка, чтобы закрепить смысл:
| Что вы хотите | Как читается правило | Компаратор возвращает |
|---|---|---|
| По возрастанию | «меньшее раньше» | |
| По убыванию | «большее раньше» | |
4. Мини‑приложение: список задач и сортировка
Чтобы сортировка была не абстрактной «отсортируем массив чисел (ура…)», продолжим учебный сюжет: у нас есть простейший список задач. Мы уже умеем хранить элементы в std::vector, умеем делать struct, умеем печатать — теперь добавим сортировку задач по разным правилам.
Пусть модель данных будет такая:
#include <string>
struct Task {
int id{};
std::string title;
int priority{}; // 1..5 (5 — очень важно)
bool done{};
};
Сделаем маленькую функцию печати одной задачи, чтобы не раздувать примеры:
#include <iostream>
#include <string>
struct Task {
int id{};
std::string title;
int priority{};
bool done{};
};
void print_task(const Task& t) {
std::cout << "#" << t.id << " [" << t.priority << "] "
<< (t.done ? "[done] " : "[todo] ")
<< t.title << '\n';
}
Сортировка по названию
Теперь создадим несколько задач и отсортируем, например, по названию (по алфавиту). Для этого нужен компаратор по title:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task { int id{}; std::string title; int priority{}; bool done{}; };
bool by_title(const Task& a, const Task& b) {
return a.title < b.title;
}
int main() {
std::vector<Task> tasks{{2,"Wash dishes",2,false},{1,"Buy milk",3,true}};
std::sort(tasks.begin(), tasks.end(), by_title);
for (const Task& t : tasks) std::cout << t.title << '\n';
// Buy milk
// Wash dishes
}
Здесь происходит важная “психологическая” вещь: сортировка struct — это просто сортировка по выбранному полю. Компаратор — это правило, которое вы бы сформулировали словами: «сортировать задачи по названию».
Сортировка по приоритету
Когда сортируем по числам, всё похоже, но появляется практический момент: объекты Task могут быть “тяжелее” (там строка), и копировать их ради сравнения не хочется. Поэтому компаратор почти всегда принимает параметры по const&. Это и быстрее, и честнее: компаратор не должен менять элементы, он только сравнивает.
Сортировка по приоритету “сначала самые важные” выглядит так:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task { int id{}; std::string title; int priority{}; bool done{}; };
bool by_priority_desc(const Task& a, const Task& b) {
return a.priority > b.priority; // больший приоритет раньше
}
int main() {
std::vector<Task> tasks{{1,"Buy milk",3,true},{2,"Wash dishes",2,false},{3,"Exam",5,false}};
std::sort(tasks.begin(), tasks.end(), by_priority_desc);
for (const Task& t : tasks) std::cout << t.priority << " " << t.title << '\n';
// 5 Exam
// 3 Buy milk
// 2 Wash dishes
}
Снова читаем компаратор как правило: «если приоритет больше — задача должна стоять раньше». И это прям то, что нам нужно.
Несколько критериев: done и priority
В реальных задачах почти всегда нужно не “одно поле”, а комбинация. Типичный сценарий для TODO‑листа: сначала показываем невыполненные задачи, а выполненные отправляем вниз (пусть отдыхают). А среди невыполненных — сначала важные.
Компаратор для такого правила обычно пишется как обычная логика if. Главное — помнить: компаратор должен вернуть true ровно тогда, когда a должен быть раньше b.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task { int id{}; std::string title; int priority{}; bool done{}; };
bool by_done_then_priority(const Task& a, const Task& b) {
if (a.done != b.done) return a.done < b.done; // todo (false) раньше done (true)
return a.priority > b.priority; // внутри группы: важное раньше
}
int main() {
std::vector<Task> tasks{{1,"Buy milk",3,true},{2,"Exam",5,false},{3,"Wash dishes",2,false}};
std::sort(tasks.begin(), tasks.end(), by_done_then_priority);
for (const Task& t : tasks) std::cout << (t.done ? "done " : "todo ") << t.title << '\n';
// todo Exam
// todo Wash dishes
// done Buy milk
}
Тут полезно заметить маленький трюк: a.done < b.done работает, потому что false < true. Это читается как «невыполненные раньше выполненных». Можно написать и более явно, но пока такой вариант вполне понятен, если вы себе проговорили смысл.
Чтобы визуально уложить “многоступенчатый” компаратор в голове, можно представлять его как мини‑блок‑схему:
flowchart TD
A[Сравнить a и b] --> B{done отличается?}
B -- да --> C[невыполненные раньше]
B -- нет --> D{priority отличается?}
D -- да --> E[больший priority раньше]
D -- нет --> F[можно считать равными по правилу]
Это не “как работает sort внутри”, а именно “как работает правило порядка”, которое вы задаёте.
5. Строгий компаратор: почему <= — ловушка
Сейчас будет момент “серьёзного взрослого программирования”, но без занудства. std::sort предполагает, что ваш компаратор задаёт строгий порядок. На практике это означает, что для любого элемента x должно быть неверно comp(x, x).
Если вы пишете return a.priority <= b.priority;, то для одинаковых priority получится true и для (a,b), и для (b,a), и даже для (a,a). Алгоритм сортировки от такого правила начинает страдать: он ожидает, что «раньше» — это не то же самое, что «не позже».
Сравните два компаратора:
bool bad(const Task& a, const Task& b) {
return a.priority <= b.priority; // плохо
}
bool good(const Task& a, const Task& b) {
return a.priority < b.priority; // хорошо
}
Первый компаратор отвечает на вопрос “a не больше b?”, а нам нужен ответ “a должен идти раньше b?”. Эти вопросы похожи, но не идентичны. Для порядка “раньше/позже” обычно используют строгое сравнение.
Если вы хотите “по возрастанию или равно”, это не компаратор, это уже критерий типа «не нарушает ли порядок». std::sort работает именно с понятием «раньше».
Отдельная мысль: компаратор не должен быть “случайным”, не должен печатать что-то на экран и не должен менять элементы. sort может вызывать компаратор много раз и в неожиданном порядке, поэтому любое побочное действие превращает отладку в сериал на 8 сезонов.
6. После sort нельзя доверять старым индексам
После сортировки меняется порядок элементов, а значит, меняются индексы. Это кажется очевидным, но именно на этом часто ломаются первые проекты.
Представьте, что вы нашли задачу с id == 10, запомнили её индекс pos, потом отсортировали tasks по приоритету… и продолжили использовать tasks[pos], думая, что там всё ещё задача id == 10. Нет, там теперь “кто-то другой”, потому что сортировка переставила элементы.
Правильная привычка такая: если вам нужен стабильный “идентификатор”, используйте поле id, а не индекс. А индекс — это просто текущая позиция в текущем порядке.
Мини‑пример (только демонстрация идеи):
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{10, 5, 7};
int pos = 0; // думаем, что "наш элемент" — это v[0] == 10
std::sort(v.begin(), v.end());
std::cout << v[pos] << '\n'; // 5 (а не 10!)
}
7. Типичные ошибки при работе с std::sort и компараторами
Ошибка №1: забыли подключить <algorithm>.
Самая простая, но очень частая история: вы пишете std::sort(...), а компилятор говорит, что он не знает, что это. В отличие от <iostream>, алгоритмы живут в своём заголовке. Это не придирка, а модель стандартной библиотеки: подключаем только то, что используем.
Ошибка №2: компаратор написан через <= или >=.
Такой компаратор часто выглядит “логично”, потому что в математике “не больше” звучит корректно. Но для сортировки нужен именно строгий порядок “раньше/позже”. <= легко делает правило противоречивым: получается, что a может быть “раньше” b, и одновременно b может быть “раньше” a. А сортировка от такого начинает нервничать.
Ошибка №3: компаратор возвращает true, когда элементы равны.
Это частный случай предыдущей ошибки, но настолько популярный, что заслуживает отдельного упоминания. Если ваш компаратор говорит, что элемент “раньше самого себя”, вы ломаете базовую логику порядка. Даже если “на тестах вроде работает”, это не значит, что так можно.
Ошибка №4: компаратор пытается что-то менять или печатать.
Иногда хочется “посмотреть, как сортировка сравнивает элементы”, и вставить std::cout внутрь компаратора. Формально это может что-то вывести, но вы получите очень странный лог: сортировка вызывает сравнение много раз и не обязана идти “слева направо”. А если компаратор ещё и меняет данные — результат будет непредсказуемым.
Ошибка №5: сортируют const‑контейнер или «внутренности», которые нельзя менять.
std::sort переставляет элементы местами. Поэтому const std::vector<Task> отсортировать нельзя: это противоречит const. Если вам нужен “отсортированный вид” без изменения исходных данных — это уже другая стратегия (но сегодня мы её не рассматриваем).
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ