Quelle est la complexité temporelle de l'opération de recherche d'un élément par clé dans std::unordered_map?

La complexité temporelle de la recherche d'un élément par clé dans std::unordered_map est en moyenne O(1) — un temps constant, grâce à l'utilisation d'une table de hachage.

Cependant, dans le pire des cas (par exemple, en cas de nombreuses collisions), la complexité peut se dégrader à O(n), où n est le nombre d'éléments dans le conteneur.

Exemple d'utilisation:

#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()) {
        // Accès à l'élément en moyenne en O(1)
        int value = it->second;
    }
}