Jaka jest złożoność czasowa operacji wyszukiwania elementu po kluczu w std::unordered_map?

Złożoność czasowa wyszukiwania elementu po kluczu w std::unordered_map wynosi średnio O(1) — czas stały, dzięki użyciu tablicy haszującej.

Jednak w najgorszym przypadku (np. przy dużej liczbie kolizji) złożoność może się pogorszyć do O(n), gdzie n to liczba elementów w kontenerze.

Przykład użycia:

#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()) {
        // Dostęp do elementu w średnim czasie O(1)
        int value = it->second;
    }
}