Koja je vremenska složenost operacije pretraživanja elementa po ključe u std::unordered_map?

Vremenska složenost pretraživanja elementa po ključu u std::unordered_map je u proseku O(1) — konstantno vreme, zahvaljujući korišćenju hash tabele.

Međutim, u najgorem slučaju (na primer, pri velikom broju kolizija) složenost može opasti na O(n), gde je n broj elemenata u kontejneru.

Primer upotrebe:

#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()) {
        // Prosečno pristup u O(1)
        int value = it->second;
    }
}