Кога трябва да използвате std::set и кога…

std::set и std::unordered_set се използват за съхраняване на уникални елементи. Изборът между тях зависи от приоритетите: подредба или производителност при достъп/вмъкване/изтриване.

std::set се базира на балансирано двоично дърво за търсене (обикновено червено-черно дърво).

Характеристики на std::set:

Елементите се съхраняват в сортиран ред.
Вмъкването, изтриването и търсенето на елементи отнема средно O(log N), където N е броят на елементите.
Подходящо е, когато важи сортирания ред на елементите или когато е необходимо да се получат елементи в определен диапазон.

std::unordered_set се базира на хеш таблица.

Характеристики на std::unordered_set:

Елементите не се съхраняват в сортиран ред.
Вмъкването, изтриването и търсенето на елементи средно отнема O(1), но в най-лошия случай (при много колизии в хеш функцията) може да достигне O(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> подреден_set;
    подреден_set.insert(5);
    подреден_set.insert(2);
    подреден_set.insert(8);

    // Елементите ще се изведат в сортиран ред: 2 5 8
    for (int стойност : подреден_set) {
        std::cout << стойност << " ";
    }
    std::cout << std::endl;

    return 0;
}

Пример за използване на std::unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> несортиран_set;
    несортиран_set.insert(5);
    несортиран_set.insert(2);
    несортиран_set.insert(8);

    // Поредността на изхода може да варира
    for (int стойност : несортиран_set) {
        std::cout << стойност << " ";
    }
    std::cout << std::endl;

    return 0;
}

Кога трябва да използвате std::set и кога std::unordered_set в C++?