Qual è la complessità temporale dell'operazione di ricerca di un elemento per chiave in std::unordered_map?

La complessità temporale di ricerca di un elemento per chiave in std::unordered_map è in media O(1) — tempo costante, grazie all'uso di una tabella hash.

Tuttavia, nel caso peggiore (ad esempio, con molte collisioni), la complessità può degradare a O(n), dove n è il numero di elementi nel contenitore.

Esempio di utilizzo:

#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()) {
        // Accesso all'elemento in media in O(1)
        int value = it->second;
    }
}