Mekkora az időbeli komplexitású az elem keresése kulcs szerint az std::unordered_map-ban?

Az std::unordered_map kulcs szerinti elemkeresésének időbeli komplexitása átlagosan O(1) — állandó idő, a hash-tábla használatának köszönhetően.

Azonban a legrosszabb esetben (például, ha sok ütközés van) a komplexitás lecsökkenhet O(n)-re, ahol n a konténerben lévő elemek száma.

Használati példa:

#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()) {
        // Átlagosan O(1) hozzáférés
        int value = it->second;
    }
}