Какова временная сложность операций поиска, вставки и удаления элементов в std::unordered_map?

В std::unordered_map операции поиска, вставки и удаления элементов имеют амортизированную временную сложность O(1) в среднем случае. Это достигается за счёт использования хеш-таблицы, где доступ к элементам происходит по хешу ключа.

Однако в худшем случае, когда происходит большое количество коллизий (например, все ключи попадают в одну корзину), временная сложность может деградировать до O(n), где n — количество элементов в контейнере.

Таким образом:

• Поиск: амортизированно O(1), в худшем случае O(n)
• Вставка: амортизированно O(1), в худшем случае O(n)
• Удаление: амортизированно O(1), в худшем случае O(n)

Для поддержания высокой производительности важно выбирать хорошую хеш-функцию и при необходимости увеличивать размер хеш-таблицы (rehashing).