Wie ist die zeitliche Komplexität der Operation zum Suchen eines Elements nach Schlüssel in std::unordered_map?

Die zeitliche Komplexität der Suche nach einem Element anhand des Schlüssels in std::unordered_map beträgt im Durchschnitt O(1) — konstante Zeit, dank der Verwendung einer Hashtabelle.

Im schlimmsten Fall (z.B. bei vielen Kollisionen) kann die Komplexität auf O(n) abfallen, wobei n die Anzahl der Elemente im Container ist.

Beispiel für die Verwendung:

#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()) {
        // Zugriff auf das Element im Durchschnitt in O(1)
        int value = it->second;
    }
}