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

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

Пример вставки:

#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> map;
    map.insert({"key", 42}); // вставка за амортизированное O(1)
    return 0;
}

Таким образом, std::unordered_map обеспечивает эффективную вставку в среднем, но зависит от качества хеш-функции и нагрузки контейнера.

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