Када треба користити std::set, а када…

std::set и std::unordered_set се користе за чување јединствених елемената. Избор између њих зависи од приоритета: редослед или перформансе приступа/увода/брисања.

std::set се заснива на балансованом бинарном претраживачком дрвету (обично црвено-црном дрвету).

Карактеристике std::set:

Елементи су у сортираном реду.
Увод, брисање и претрага елемената трају у времену О(log N), где је N број елемената.
Погодно је када је важан сортирани ред елемената или када је потребно добијање елемената у одређеном опсегу.

std::unordered_set се заснива на хеш-табели.

Карактеристике std::unordered_set:

Елементи се не чувају у сортираном реду.
Увод, брисање и претрага елемената у просеку трају у времену О(1), али у најгорем случају (при великом броју колизије хеш-функције) могу достићи О(N).
Потребно је да тип елемента има одређену хеш-функцију (std::hash) и оператор поређења на једнакост (operator==).
Погодно је када је потребна максимална брзина увођења, брисања и претраге, а редослед елемената није важан.

Табела поређења:

Критеријум	`std::set`	`std::unordered_set`
Унутрашња структура	Балансовано дрво	Хеш-табела
Редослед елемената	Сортиран	Неспортиран
Време претраге/увода/брисања (просек)	O(log N)	O(1)
Време претраге/увода/брисања (најгоре)	O(log N)	O(N)
Захтеви за тип	Оператор `<`	`std::hash`, `operator==`

Пример коришћења std::set:

#include <iostream>
#include <set>

int main() {
    std::set<int> ordered_set;
    ordered_set.insert(5);
    ordered_set.insert(2);
    ordered_set.insert(8);

    // Елементи ће бити исписани у сортираном реду: 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Пример коришћења std::unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> unordered_set;
    unordered_set.insert(5);
    unordered_set.insert(2);
    unordered_set.insert(8);

    // Редослед исписа може бити различит
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Када треба користити std::set, а када std::unordered_set у C++?