std::sort і компаратор — базовий сценарій сортування

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 означає «більше число має стояти раніше». І так, спершу це трохи збиває з пантелику, але потім стає дуже зручно: ви буквально записуєте правило порядку.

Невелика таблиця, щоб закріпити ідею:

true

a < b

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

У реальних задачах майже завжди потрібне не «одне поле», а комбінація критеріїв. Типовий сценарій для списку задач: спочатку показуємо невиконані задачі, а виконані відправляємо вниз — нехай відпочивають. А серед невиконаних спочатку йдуть важливіші.

Компаратор для такого правила зазвичай пишуть як звичайну логіку 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 може викликати його багато разів і в несподіваному порядку, тому будь‑яка побічна дія перетворює налагодження на серіал із восьми сезонів.

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. Якщо вам потрібен «відсортований вигляд» без зміни початкових даних, це вже інша стратегія (але сьогодні ми її не розглядаємо).