Wat is de tijdcomplexiteit van de zoekoperatie op een element op sleutel in std::unordered_map?

De tijdscomplexiteit van het zoeken van een element op sleutel in std::unordered_map is gemiddeld O(1) — constante tijd, dankzij het gebruik van een hash-tabel.

In het slechtste geval (bijvoorbeeld bij veel collisions) kan de complexiteit afnemen tot O(n), waarbij n het aantal elementen in de container is.

Voorbeeld van gebruik:

#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()) {
        // Toegang tot het element in gemiddeld O(1)
        int value = it->second;
    }
}