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

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

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

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

#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> map;
    map["key"] = 42;
    auto it = map.find("key");
    if (it != map.end()) {
        // Доступ к элементу за O(1) в среднем
        int value = it->second;
    }
}