Care este complexitatea temporală a căutării unui element după cheie în std::unordered_map?

Complexitatea temporară a căutării unui element după cheie în std::unordered_map în cazul mediu este O(1), adică constantă. Acest lucru se realizează prin utilizarea unui tabel de dispersie, unde cheile sunt hash-uite și elementele sunt distribuite în coșuri.

Totuși, în cel mai rău caz, când apar multe coliziuni (de exemplu, toate cheile cad în același coș), complexitatea poate degrada la O(n), unde n este numărul de elemente din container.

Exemplu de utilizare:

#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 << "Găsit: " << it->second << std::endl;
    }
    return 0;
}