Qual é a complexidade temporal da operação de busca de um elemento por chave em std::unordered_map?

A complexidade temporal da pesquisa de um elemento por chave em std::unordered_map é em média O(1) — tempo constante, devido ao uso de uma tabela de hash.

No entanto, no pior caso (por exemplo, com muitas colisões), a complexidade pode degradar-se para O(n), onde n é o número de elementos no contêiner.

Exemplo de uso:

#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()) {
        // Acesso ao elemento em média em O(1)
        int value = it->second;
    }
}