Какова асимптотическая сложность операций для контейнеров unordered_set и set в C++?

Асимптотическая сложность операций для std::unordered_set и std::set в C++17:

• std::unordered_set основан на хеш-таблице. Средний случай сложности O(1) достигается при хорошей хеш-функции и отсутствии большого количества коллизий. Худший случай O(n) возникает при сильных коллизиях (например, все элементы хешируются в один бакет) или при неэффективном распределении элементов.
• std::set основан на сбалансированном бинарном дереве поиска (обычно красно-черном дереве). Сложность O(log n) обусловлена логарифмической высотой дерева, где n — количество элементов.

Важные заметки:

• Худший случай для std::unordered_set вставка и удаление может включать рехеширование, что при надобности перестроить всю таблицу займет O(n).
• Операция доступа для std::set через итератор также имеетлогаррифмическую сложность.

#include <unordered_set> // Для unordered_set
#include <set>           // Для set

// Пример использования std::unordered_set
std::unordered_set<int> uset;
uset.insert(10); // Средний O(1), Худший O(n)
uset.find(10);   // Средний O(1), Худший O(n)
uset.erase(10);  // Средний O(1), Худший O(n)

// Пример использования std::set
std::set<int> s;
s.insert(10); // O(log n)
s.find(10);   // O(log n)
s.erase(10);  // O(log n)