¿Cuál es la complejidad temporal de la operación de búsqueda de un elemento por clave en std::unordered_map?

La complejidad temporal de buscar un elemento por clave en std::unordered_map en promedio es O(1) — tiempo constante, gracias al uso de una tabla hash.

Sin embargo, en el peor de los casos (por ejemplo, cuando hay muchas colisiones), la complejidad puede degradarse a O(n), donde n es la cantidad de elementos en el contenedor.

Ejemplo 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()) {
        // Acceso al elemento en promedio en O(1)
        int value = it->second;
    }
}