Асимптотическая сложность операций для std::unordered_set и std::set в C++17:
| Операция | std::unordered_set (средний случай) | std::unordered_set (худший случай) | std::set |
|---|---|---|---|
| Вставка (insert) | O(1) | O(n) | O(log n) |
| Удаление (erase) | O(1) | O(n) | O(log n) |
| Поиск (find) | O(1) | O(n) | O(log n) |
| Доступ | Неприменимо | Неприменимо | O(log n) (итератор) |
std::unordered_set основан на хеш-таблице. Средний случай сложности O(1) достигается при хорошей хеш-функции и отсутствии большого количества коллизий. Худший случай O(n) возникает при сильных коллизиях (например, все элементы хешируются в один бакет) или при неэффективном распределении элементов.std::set основан на сбалансированном бинарном дереве поиска (обычно красно-черном дереве). Сложность O(log n) обусловлена логарифмической высотой дерева, где n — количество элементов.Важные заметки:
std::unordered_set вставка и удаление может включать рехеширование, что при надобности перестроить всю таблицу займет O(n).std::set через итератор также имеетлогаррифмическую сложность.c