Kokia yra elementų paieškos operacijos laiko sudėtingumas pagal raktą std::unordered_map?

std::unordered_map paieškos elemento pagal raktą laiko sudėtingumas vidutiniškai yra O(1) — pastovus laikas, dėka hash lentelės naudojimo.

Tačiau blogiausiu atveju (pavyzdžiui, kai yra daug kolizijų) sudėtingumas gali sumažėti iki O(n), kur n yra konteinerio elementų skaičius.

Naudojimo pavyzdys:

#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()) {
        // Vidutiniškai prieiga per O(1)
        int value = it->second;
    }
}