Aká je časová zložitosť operácie vyhľadávania prvku podľa kľúča v std::unordered_map?

Časová zložitosť vyhľadávania prvku podľa kľúča v std::unordered_map je v priemere O(1) — konštantný čas, vďaka použitiu hash tabuľky.

Avšak v najhoršom prípade (napríklad pri veľkom počte kolízií) sa zložitosť môže zhoršiť na O(n), kde n je počet prvkov v kontajneri.

Príklad použitia:

#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()) {
        // Priemerný prístup v O(1)
        int value = it->second;
    }
}