Контракт компаратора для std::map / std::set

1. Навіщо map/set компаратор

Якщо раніше ви сприймали компаратор як «штуку для сортування», то в map/set його роль набагато важливіша. Ці контейнери зберігають елементи в упорядкованому вигляді: усередині вони підтримують структуру даних на кшталт дерева пошуку. Саме компаратор підказує дереву, куди рухатися під час пошуку або вставки: ліворуч чи праворуч.

В офіційній специфікації стандартної бібліотеки це формулюють так: елементи контейнера впорядковані відносно comp (порівнювача). Навіть вислів «sorted with respect to comp» трапляється у формулюваннях про асоціативні контейнери.

Практичний висновок простий: компаратор — не «опція форматування», а частина логіки коректності. Неправильний компаратор перетворює дерево на лабіринт, у якому таблички «праворуч до виходу» інколи ведуть просто в стіну.

std::sort vs std::set: порядок і унікальність

Тут є важливий момент, який часто плутають. Під час сортування повтори допустимі: ви можете відсортувати вектор так, що два різні елементи будуть «еквівалентними» для компаратора, наприклад рядки однакової довжини. std::vector від цього не ламається: він просто отримує один із коректних порядків.

А от у std::set (і в std::map за ключем) компаратор задає не лише порядок, а й критерій того, чи вважає контейнер два ключі «однаковими». У документах і обговореннях стандарту для цього використовують термін «equivalent keys» — еквівалентні ключі.

У «шкільному» формулюванні це зазвичай пояснюють так:

Ключі `a` і `b` вважаються еквівалентними для `map/set`, якщо водночас
`comp(a, b) == false` і `comp(b, a) == false`.

Тобто контейнер не питає, чи a == b. Він питає: «Чи справді ні a менше за b, ні b менше за a?»

Чому так зроблено? Тому що дерево пошуку працює за логікою «менше/більше», і саме її воно розуміє найкраще.

2. Strict weak ordering: контракт компаратора

Термін strict weak ordering звучить як закляття з академії чарівників, але на практиці це просто набір здорових правил, які роблять порівняння схожим на звичне <.

Щоб не потонути у формальностях, зведімо все до трьох ідей: строгість, узгодженість і адекватна еквівалентність.

Нижче — зручна «шпаргалкова» таблиця. Вона не замінює стандарт, але добре показує, чому одні компаратори працюють роками, а інші — лише до першого дедлайну.

Тут і зʼявляється важлива побутова інтерпретація.

Уявіть, що компаратор — це турнікет, який вирішує, кого пропустити в черзі раніше. Strict weak ordering означає ось що: турнікет не має змінювати настрій, не має вважати людину «ранішою за саму себе» і не має створювати циклів на кшталт «А раніше Б, Б раніше В, а В раніше А». Інакше черга перетворюється на суперечку на кухні: «Ні, ти перший!», «Ні, ти!», «Та я взагалі в іншому підʼїзді».

3. Як ламають set: мініприклади

Зараз буде серія коротких прикладів. Вони спеціально маленькі, щоб ви могли одразу вловити суть, а не потонути в інфраструктурі.

Антипатерн: використовувати <= замість <

Важливо: компаратор для set/map має відповідати на запитання «строго менше?». Тому <= майже завжди означає помилку.

#include <set>

struct BadCompare {
    bool operator()(int a, int b) const {
        return a <= b; // помилка: a <= a дає true
    }
};

int main() {
    std::set<int, BadCompare> s;
    s.insert(1);
    s.insert(2);
}

Чому це погано? Тому що за a == a компаратор каже: «так, a менше за a». Це порушує строгість: comp(x, x) має бути false.

«Склеювання» різних ключів: порівняння лише за частиною даних

Припустімо, ми хочемо зберігати рядки в set, але «сортувати за довжиною». Здається, це логічно… доки не спробуєте вставити два різні рядки однакової довжини.

#include <set>
#include <string>

struct ByLenOnly {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() < b.size(); // без tie-breaker
    }
};

int main() {
    std::set<std::string, ByLenOnly> s;
    s.insert("cat");
    s.insert("dog"); // не додасться: еквівалентний "cat" за компаратором
}

Тут контейнер вважає "cat" і "dog" еквівалентними, тому що жоден не є «меншим» за інший за довжиною. І він чесно виконує контракт set: зберігає унікальні елементи… у власному розумінні унікальності.

Правильний варіант: додаємо tie-breaker

Tie-breaker — це запасний критерій порівняння, який вмикається, коли основний критерій «дав нічию». У прикладі з рядками спочатку порівнюємо довжину, а якщо вона однакова, то порівнюємо лексикографічно.

#include <set>
#include <string>

struct ByLenThenLex {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b; // tie-breaker
    }
};

int main() {
    std::set<std::string, ByLenThenLex> s;
    s.insert("cat");
    s.insert("dog"); // тепер додасться
}

4. Внутрішня логіка set: вставка і перевірка компаратора

Як set «міркує» під час вставки

Щоб зрозуміти, чому компаратор такий важливий, корисно уявити, що під час вставки set ставить вашому компаратору багато запитань: «це лівіше чи правіше?»

flowchart TD
    A["insert(x)"] --> B["порівнюємо з поточним вузлом y"]
    B --> C{"comp(x, y)?"}
    C -->|так| L["переходимо в ліве піддерево"]
    C -->|ні| D{"comp(y, x)?"}
    D -->|так| R["переходимо в праве піддерево"]
    D -->|ні| E["еквівалентні => вважаємо, що ключ уже є"]

Ось цей третій випадок — «обидва рази false» — і пояснює, чому tie-breaker рятує ваші дані від «випадкового зникнення».

Як перевіряти компаратор на адекватність

Коли ви пишете компаратор, хочеться мати просту перевірку здорового глузду. Ніхто не вимагає від вас формальних доказів, але кілька практичних перевірок справді рятують.

Добрий старт — поставити собі три запитання на конкретних значеннях:

Перше: «Чи може comp(x, x) повернути true?» Якщо так, це майже напевно помилка. Часто причина — <=.

Друге: «Якщо в мене є два різні обʼєкти a і b, чи може статися так, що comp(a, b) і comp(b, a) обидва false?» Якщо так, це не завжди помилка, але ви маєте свідомо сказати собі: «Так, я хочу, щоб ці ключі були еквівалентними». Якщо ви цього не хочете, додавайте tie-breaker.

Третє: «Чи може компаратор утворити цикл?» Наприклад, ви порівнюєте рядки за a[0] < b[0], але для порожнього рядка додаєте якийсь дивний хак. Цикли часто зʼявляються через «особливі випадки», які суперечать основній логіці.

5. Компаратор має бути «чистим»

Дуже хочеться зробити «розумний» компаратор: наприклад, сортувати то за зростанням, то за спаданням, перемикаючи глобальний прапор. У звичайному сортуванні це вже ризиковано, але інколи ще можна якось викрутитися. У set/map це майже гарантована катастрофа.

Проблема в тому, що дерево будується за одним порядком. Якщо компаратор почне змінювати правила на ходу, дерево не має механізму перебудуватися самостійно. Воно й далі «думатиме», що «ліворуч/праворуч» означає одне, а компаратор раптом почне стверджувати інше.

Невеликий антиприклад — так робити не треба:

#include <set>

bool g_reverse = false;

struct WeirdCompare {
    bool operator()(int a, int b) const {
        if (!g_reverse) return a < b;
        return b < a; // порядок змінили "на льоту"
    }
};

int main() {
    std::set<int, WeirdCompare> s;
    s.insert(1);
    s.insert(2);

    g_reverse = true; // тепер компаратор — "інша людина"
}

Правило просте: один контейнер живе з одним фіксованим порядком.

6. Приклад: задачі за пріоритетом у std::set

Зробімо практичну привʼязку до нашого навчального мінізастосунку. Нехай у нас є проста модель задачі: id, title, priority. Раніше ми могли зберігати задачі у std::vector і сортувати їх під час виведення. Але тепер хочемо, щоб задачі завжди були доступні «за пріоритетом» без додаткового пересортування.

Для цього використаємо std::set, але тут є важливий нюанс: якщо порівнювати лише priority, то всі задачі з однаковим пріоритетом «склеяться». Тому додамо tie-breaker за id.

Модель і компаратор

#include <string>

struct Task {
    int id{};
    std::string title;
    int priority{}; // що менше, то важливіше
};

struct TaskByPriority {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.id < b.id; // tie-breaker: не "склеюємо" різні задачі
    }
};

Зверніть увагу: ми зробили компаратор детермінованим і «строгим». Він не використовує <=, а за a == a поверне false.

Зберігаємо задачі в std::set і друкуємо в порядку пріоритету

#include <iostream>
#include <set>

int main() {
    std::set<Task, TaskByPriority> tasks;

    tasks.insert(Task{1, "Write report", 2});
    tasks.insert(Task{2, "Fix bug", 1});
    tasks.insert(Task{3, "Buy coffee", 2});

    for (const auto& t : tasks) {
        std::cout << t.priority << " | " << t.id << " | " << t.title << '\n';
        // 1 | 2 | Fix bug
        // 2 | 1 | Write report
        // 2 | 3 | Buy coffee
    }
}

Тут видно дві речі. По‑перше, порядок справді визначається компаратором. По‑друге, задачі з priority == 2 обидві зберігаються в контейнері, тому що tie-breaker розрізняє їх за id.

Нюанс: чому елементи set «ніби const»

Якщо ви спробуєте зробити так: пройтися по set і змінити priority в елемента, компілятор, найімовірніше, не дозволить вам цього зробити. І справа тут не в «шкідливості» мови, а в тому, що зміна поля, яке впливає на порядок, руйнує дерево.

Логіка проста: якщо елемент «був ліворуч», а після зміни має «бути праворуч», дерево саме про це не дізнається. Тому set захищає себе: ключі всередині не можна змінювати напряму.

Якщо вам треба «змінити пріоритет», коректна стратегія — видалити стару версію задачі й вставити нову. Інший варіант — зберігати джерело правди окремо, а в set тримати ключі або індекси. Але це вже окрема велика тема, і сьогодні ми її не розвиватимемо.

7. Типові помилки під час написання компаратора для map/set

Помилка № 1: використовувати <= або >= замість строгого <.
Це найчастіша проблема: здається, що «так навіть надійніше, адже рівні теж враховуємо». Але компаратор у set/map має відповідати саме на запитання «строго менше?». Якщо comp(x, x) стає true, ви ламаєте базову ідею strict weak ordering, і контейнер більше нічого не зобовʼязаний.

Помилка № 2: думати, що унікальність ключів визначається через operator==.
Після векторів і std::find дуже хочеться «звичної рівності». Але set/map працюють за правилом «менше». Якщо компаратор не розрізняє два різні ключі — тобто обидва порівняння дають false — контейнер вважатиме їх еквівалентними. І це нормально, просто про це треба памʼятати. Термін «equivalent keys» у контексті асоціативних контейнерів трапляється в обговореннях формулювань стандарту.

Помилка № 3: порівнювати лише за одним полем і випадково «склеювати» різні ключі.
Дуже типовий сценарій: сортуємо за «основною ознакою», наприклад за пріоритетом, а про інші поля забуваємо. У результаті set починає «втрачати» елементи під час вставки. Виправлення зазвичай просте: додайте tie-breaker, найчастіше за id або за «другим полем».

Помилка № 4: робити компаратор залежним від зовнішнього змінюваного стану.
Компаратор, який читає глобальний прапор «сортувати за зростанням/спаданням», здається зручним. Але дерево будується під один порядок, і якщо змінити логіку порівняння посеред життя контейнера, структура даних стане самосуперечливою. Контейнер може почати «не знаходити» те, що в ньому є.

Помилка № 5: додавати побічні ефекти в компаратор.
Іноді хочеться «подивитися, скільки разів викликається компаратор», і рука тягнеться до std::cout або до інкременту лічильника. Це небезпечно: порівняння викликається багато разів, у несподівані моменти, а порядок викликів не зобовʼязаний бути «гарним». Компаратор має бути максимально чистим: порівняв — відповів — і все.

Помилка № 6: намагатися змінювати ключі в set на місці.
У set елементи фактично не можна редагувати напряму не просто так: зміна полів, які беруть участь у порівнянні, руйнує порядок дерева. Якщо вам потрібно «змінити пріоритет» або «перейменувати ключ», зазвичай правильніше видалити елемент і вставити новий. Сама ідея того, що асоціативні контейнери підтримують упорядкованість відносно comp, зафіксована у формулюваннях вимог до них.