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

Для 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)

Таблица сравнения: