set / unordered_set

1. Вступ

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

Множина в програмуванні — це ніби список гостей на вечірці, де охорона працює суворо: «того самого гостя двічі не пускаємо». До того ж вона вміє дуже швидко відповідати на головне запитання: «Ця людина вже всередині?». У C++ такими «списками гостей» є std::set і std::unordered_set.

std::set і std::unordered_set: що це таке і чим вони відрізняються

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

std::set<T> зберігає елементи у відсортованому порядку (за правилом порівняння, найчастіше — за <). Тому, якщо ви перебираєте set циклом, елементи йтимуть за зростанням (для рядків — за лексикографічним порядком).

std::unordered_set<T> зберігає елементи «у хеш-таблиці». Порядок обходу там не є впорядкованим, тож на нього не можна покладатися. Зате перевірка «чи є елемент» зазвичай дуже швидка.

Невелика таблиця, щоб закріпити загальну картину:

std::set<T>

std::unordered_set<T>

І так, обидва контейнери входять до стандартної бібліотеки C++, зокрема й unordered_set.

2. Базові операції: insert, contains/find, erase

Будь-який контейнер стає «вашим другом», щойно ви впевнено вмієте робити три речі: додавати елементи, перевіряти їхню наявність і видаляти. Для множин це якраз найуживаніші операції, і в C++ вони виглядають доволі дружньо, якщо не боятися ітераторів.

Додавання: insert і що він повертає

Коли ви додаєте елемент у set або unordered_set, контейнер або вставляє його (якщо такого ще не було), або мовчки нічого не робить (якщо елемент уже є). І щоб ви не гадали: «а що сталося?», insert повертає пару: ітератор і прапорець bool. Прапорець показує, чи справді відбулася вставка, чи елемент уже був у множині.

Приклад на std::set:

#include <iostream>
#include <set>

int main() {
    std::set<int> s;

    auto [it1, ok1] = s.insert(10);
    auto [it2, ok2] = s.insert(10);

    std::cout << ok1 << ' ' << ok2 << '\n'; // 1 0
}

Тут ok1 == true, бо значення 10 уперше зʼявилося в множині. А ok2 == false, бо вдруге «такого гостя вже всередину не пустили».

Перевірка «чи є елемент»: contains, find і count

Перевіряти наявність елемента можна по-різному. У сучасному C++ (C++20+) є зручний метод contains, який повертає true/false. Якщо ваш компілятор підтримує C++23 (а в курсі ми використовуємо саме його), contains — чудовий вибір, коли треба «просто перевірити».

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> banned{"spam", "ads"};

    std::cout << banned.contains("spam") << '\n'; // 1
    std::cout << banned.contains("news") << '\n'; // 0
}

Якщо з якоїсь причини contains недоступний (або вам потрібно не просто «так/ні», а ще й ітератор), використовуйте find. Він повертає ітератор: або на знайдений елемент, або end().

#include <iostream>
#include <set>

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

    if (auto it = s.find(2); it != s.end()) {
        std::cout << "found: " << *it << '\n'; // found: 2
    } else {
        std::cout << "not found\n";
    }
}

Є ще метод count(x). Для множини він повертає 0 або 1 (бо повторів немає). Іноді це зручно, але в навчальному коді частіше читабельніше виглядає contains.

Видалення: erase(value) повертає «скільки видалили»

Для видалення елемента за значенням є метод erase(value). Він повертає кількість видалених елементів. Для set/unordered_set це майже завжди 0 або 1, і це зручно: можна відразу зрозуміти, чи видалення спрацювало, чи елемента взагалі не було.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> s{1, 2, 3};

    std::size_t removed1 = s.erase(2);
    std::size_t removed2 = s.erase(42);

    std::cout << removed1 << ' ' << removed2 << '\n'; // 1 0
}

3. Практичні прийоми: прибрати дублікати й не ламати set

Прибираємо дублікати: «фільтр унікальності»

Майже магічний трюк: ви берете список із повторюваними значеннями (наприклад, vector) і за один рядок перетворюєте його на набір унікальних значень. Це не лише зручно, а й допомагає краще мислити про задачу: ви буквально кажете коду, що вам потрібна множина, а не список.

#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 3, 2, 1};

    std::set<int> uniq(v.begin(), v.end()); // сконструювали set з діапазону

    for (int x : uniq) {
        std::cout << x << ' '; // 1 2 3
    }
    std::cout << '\n';
}

Чому тут set, а не unordered_set? Бо set ще й відсортував елементи. Якщо сортування не потрібне, можна взяти unordered_set. Але тоді порядок виведення буде «як вийде», і це нормально — якщо ви не намагаєтеся будувати на ньому логіку.

Чому елементи set не можна «просто взяти й змінити»

На перший погляд це може дивувати: у vector ми могли змінювати v[i], а в set — ні. Причина проста: у set елемент водночас є ключем, а внутрішня структура контейнера залежить саме від ключів. Якщо ви «нишком» зміните ключ, контейнер зламає сам себе: елементи опиняться «не там», пошук почне брехати, і світ стане трохи сумнішим.

Тому ітератор set поводиться як ітератор до const T. Спроба змінити елемент напряму зазвичай не скомпілюється — і це добре: компілятор рятує вас від дуже підступного бага.

Мінідемонстрація ідеї:

#include <set>

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

    auto it = s.find(2);
    // *it = 10; // так не можна: елемент у set "як ключ", змінювати його не можна
}

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

4. Навчальний застосунок TaskBox: теги через unordered_set

Щоб множини не залишилися абстрактною теорією, давайте продовжимо розвивати наш маленький консольний застосунок «TaskBox» (умовна назва): він зберігає задачі, а ми хочемо додавати до них теги й гарантувати, що тег не повторюється.

Уявімо, що в нас є struct Task, а в кожної задачі — заголовок і набір тегів. Теги — ідеальний кандидат на unordered_set<std::string>: нам важливіше швидко перевіряти, «чи є вже тег», ніж виводити теги відсортованими.

Модель задачі з тегами як unordered_set

#include <string>
#include <unordered_set>

struct Task {
    int id{};
    std::string title;
    std::unordered_set<std::string> tags; // теги без повторів
};

Тут важливо, що unordered_set зберігає унікальні рядки. Якщо користувач десять разів додасть тег "study", усередині все одно буде лише один "study".

Додаємо тег і читаємо результат insert

Тепер напишемо маленьку функцію, яка додає тег і повідомляє, чи справді його було додано.

#include <string>
#include <unordered_set>

bool AddTag(std::unordered_set<std::string>& tags, const std::string& tag) {
    auto [it, inserted] = tags.insert(tag);
    return inserted; // true, якщо тега раніше не було
}

Зверніть увагу на дизайн: ми повертаємо bool, бо для логіки застосунку важливий саме факт: «це новий тег чи ні». Ітератор it нам тут не потрібен, але insert однаково його повертає — просто тому, що API контейнера універсальний.

Використання в main: без повторів і без зайвої драми

#include <iostream>
#include <string>
#include <unordered_set>

bool AddTag(std::unordered_set<std::string>& tags, const std::string& tag) {
    auto [it, inserted] = tags.insert(tag);
    return inserted;
}

int main() {
    std::unordered_set<std::string> tags;

    std::cout << AddTag(tags, "study") << '\n'; // 1
    std::cout << AddTag(tags, "study") << '\n'; // 0
}

Це дуже «чиста» логіка: нам не потрібно писати if (!contains) push_back, не потрібно вручну бігти по вектору. Контейнер робить саме те, для чого його створили.

5. Як вибрати: set чи unordered_set

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

Якщо вам хочеться, щоб елементи під час друку йшли «гарно» — за зростанням, або ви заздалегідь знаєте, що порядок потрібен як частина поведінки програми (наприклад, ви виводите «список дозволених команд» у відсортованому вигляді), беріть set.

Якщо вам потрібно багато швидких перевірок «є/немає» і порядок не важливий (наприклад, перевірка заборонених слів, тегів, ідентифікаторів), беріть unordered_set. У більшості прикладних задач «перевірка належності» — саме те місце, де unordered_set відчувається особливо природно.

Невелика схема-підказка (не ідеальна, але чесна) може виглядати так:

flowchart TD
    A["Потрібен контейнер унікальних значень"] --> B{"Важливий порядок обходу?"}
    B -->|Так| C["std::set<T> (упорядкований)"]
    B -->|Ні| D{"Часто перевіряємо наявність?"}
    D -->|Так| E["std::unordered_set<T> (зазвичай швидше)"]
    D -->|Ні / не принципово| E

Сенс тут не в «математичній строгості», а в тому, щоб ваш мозок щоразу не починав заново винаходити колесо.

6. Типові помилки під час роботи з set і unordered_set

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

Помилка № 2: ігнорувати bool з insert, хоча для логіки важливо знати, чи вставилося значення.
Новачок часто робить s.insert(x) і думає: «ну вставилося та й вставилося». А потім пише код, де треба відрізнити «ми вперше побачили цей тег» від «тег уже був». У таких місцях auto [it, ok] = insert(...) — це не бюрократія, а корисна інформація, яку контейнер спеціально повертає, щоб ви не гадали.

Помилка № 3: розіменовувати результат find без перевірки it != end().
Схема роботи з ітераторами тут майже завжди однакова: find або повертає ітератор на елемент, або end(). Якщо одразу робити *it, ви отримаєте невизначену поведінку (а вона, як відомо, іноді працює… щоб потім раптово зробити вам боляче). Тому спочатку перевірка, потім доступ.

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

Помилка № 5: використовувати set там, де вам насправді потрібна частота появ.
Іноді людина бачить «унікальність» і думає: «О, значить set допоможе порахувати, скільки разів трапилося слово». Але set зберігає лише факт наявності. Якщо вам потрібна частота, зазвичай це вже задача для словника: «значення → лічильник» (тобто map/unordered_map). У сьогоднішній лекції ми в це не заглиблюємося, але важливо не плутати «унікальність» і «кількість появ».