Какова временная сложность поиска элемента по ключу в std::unordered_map?

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

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

Пример использования:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
    auto it = map.find(2);
    if (it != map.end()) {
        std::cout << "Found: " << it->second << std::endl;
    }
    return 0;
}