Для std::set (основан на сбалансированном двоичном дереве поиска):
insert одного элемента): O(log N)erase одного элемента): O(log N)find): O(log N)Для std::unordered_set (основан на хеш-таблице):
insert одного элемента): O(1)erase одного элемента): O(1)find): O(1)insert одного элемента): O(N)erase одного элемента): O(N)find): O(N)Таблица сравнения:
| Операция | std::set | std::unordered_set (в среднем) | std::unordered_set (в худшем случае) |
|---|---|---|---|
| Вставка единичного элемента | O(log N) | O(1) | O(N) |
| Удаление единичного элемента | O(log N) | O(1) | O(N) |
| Поиск единичного элемента | O(log N) | O(1) | O(N) |