Quelle est la complexité asymptotique des opérations effectuées avec les conteneurs unordered_set et set en 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)

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

Операция	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)