set и unordered_set — это два разных контейнера из стандартной библиотеки C++ (<set> и <unordered_set> соответственно), предназначенные для хранения уникальных элементов. Однако они отличаются принципами внутреннего устройства, временем выполнения операций, порядком хранения элементов и требованиями к типам данных.

📦 set

🔹 Определение

std::set<int> mySet;

• Основан на самобалансирующемся двоичном дереве поиска (обычно Red-Black Tree).

• Все элементы отсортированы по возрастанию (или по пользовательскому компаратору).

• Все элементы уникальны.

🔹 Время выполнения операций

🔹 Особенности

• Элементы автоматически отсортированы.

• Можно удобно использовать итераторы для получения диапазона значений.

• Поддерживает lower_bound, upper_bound, equal_range и другие методы, завязанные на порядок.

🧺 unordered_set

🔹 Определение

std::unordered_set<int> myUnorderedSet;

• Основан на хэш-таблице.

• Элементы не отсортированы, порядок произвольный.

• Все элементы также уникальны.

🔹 Время выполнения операций (в среднем)

🔹 Особенности

• Очень быстрый доступ по хэшу.

• Нет сортировки.

• Требует, чтобы тип поддерживал:

  • std::hash<T> — хэш-функция.

  • operator== — для сравнения элементов.

⚙️ Внутреннее устройство

🧪 Примеры

set:

std::set<int> s;
s.insert(5);
s.insert(1);
s.insert(3);
// Вывод: 1 3 5
for (int val : s)
std::cout << val << " ";
#### **unordered_set:**
std::unordered_set&lt;int&gt; us;
us.insert(5);
us.insert(1);
us.insert(3);
// Вывод: порядок не определён, например: 3 1 5
for (int val : us)
std::cout << val << " ";

🔍 Пример использования с пользовательским типом

Для unordered_set:

Нужен std::hash<MyType> и operator==:
struct Point {
int x, y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
namespace std {
template <>
struct hash&lt;Point&gt; {
size_t operator()(const Point& p) const {
return hash&lt;int&gt;()(p.x) ^ (hash&lt;int&gt;()(p.y) << 1);
}
};
}
std::unordered_set&lt;Point&gt; points;
points.insert({1, 2});

Для set:

Нужен operator<:
struct Point {
int x, y;
bool operator<(const Point& other) const {
return x == other.x ? y < other.y : x < other.x;
}
};
std::set&lt;Point&gt; points;
points.insert({1, 2});

🧮 Где использовать set, а где unordered_set

🧠 Память и аллокации

• set использует дерево → больше указателей, выделений памяти на каждый узел.

• unordered_set использует большой массив бакетов (таблицу), но может потреблять больше памяти из-за запасов на перераспределение.

🛠️ Особенности реализации

• unordered_set может работать хуже, если:

  • плохая хэш-функция,

  • часто происходят коллизии (много значений попадает в одну корзину),

  • маленький размер таблицы (нужно правильно задавать reserve()).

Пример коллизии:

std::unordered_set<int> us;
us.reserve(1000); // уменьшает количество перераспределений

🔐 Потокобезопасность

• И set, и unordered_set не потокобезопасны.

• Если нужно использовать в нескольких потоках — нужны блокировки или структуры из concurrent-библиотек.

🔚 Итоговое сравнение (таблица)

Таким образом, set и unordered_set — два мощных инструмента, подходящих для разных задач. Один обеспечивает сортировку и устойчивую производительность, другой — высокую скорость доступа без гарантированного порядка.