Ausführbare C++-Docs: unordered_map

Q: Was ist der Unterschied zwischen map und unordered_map in C++?

std::map ist ein balancierter Binärbaum: Die Schlüssel bleiben sortiert und die Operationen sind O(log n). std::unorderedmap ist eine Hashtabelle: Die Schlüssel haben keine bestimmte Reihenfolge, aber Einfügen und Nachschlagen sind im Durchschnitt O(1). Verwende unorderedmap, wenn du nur schnelles Nachschlagen per Schlüssel brauchst und dir die Reihenfolge egal ist; verwende map, wenn du sortierte Iteration oder Bereichsabfragen brauchst.

Q: Fügt unordered_map[] einen Schlüssel ein, wenn er nicht existiert?

Ja. m[key] konstruiert standardmäßig und fügt den Schlüssel ein, wenn er fehlt, und gibt dann eine Referenz darauf zurück. Das bedeutet, dass selbst ein wie ein Lesezugriff aussehendes if (m[key] == ...) die map stillschweigend wachsen lässt. Um die Zugehörigkeit zu prüfen, ohne einzufügen, verwende stattdessen m.count(key) oder m.find(key).

Q: Ist unordered_map in C++ immer schneller als map?

Nein. Es ist im Durchschnitt O(1), aber das Hashing hat einen Mehraufwand, und ein schlechter Hash (oder feindliche Schlüssel) kann das Nachschlagen auf O(n) verschlechtern. Bei kleinen Maps können die konstanten Faktoren und das schlechtere Cache-Verhalten eine sortierte map genauso schnell oder schneller machen. Miss nach, wenn es darauf ankommt, aber greife standardmäßig zu unordered_map, wenn du nur Nachschlagen per Schlüssel brauchst.

Wenn die Reihenfolge keine Rolle spielt

Du hast gerade std::map gesehen, das seine Schlüssel mithilfe eines balancierten Baums sortiert hält und dir Operationen in O(log n) bietet. Aber das Sortieren kostet etwas, und oft ist dir die Reihenfolge, in der die Schlüssel herauskommen, egal - du willst nur so schnell wie möglich fragen: „Ist dieser Schlüssel hier, und was ist sein Wert?"

Genau dafür ist std::unordered_map da. Es ist eine Hashtabelle: Sie schickt jeden Schlüssel durch eine Hash-Funktion, um zu entscheiden, wo sie ihn ablegt, wodurch Einfügen, Nachschlagen und Löschen im Durchschnitt O(1) statt O(log n) sind. Der Kompromiss ist, dass die Iterationsreihenfolge nicht festgelegt ist - die Schlüssel kommen in der Reihenfolge heraus, in der die Buckets sie zufällig halten.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

Die Schnittstelle ist absichtlich fast identisch mit der von map - oft kannst du das eine durch das andere ersetzen, indem du nur den Typ änderst. Binde <unordered_map> ein (nicht <map>), und die Schlüssel kommen unsortiert heraus.

Einfügen und Aktualisieren

Es gibt mehrere Möglichkeiten, Einträge hinzuzufügen, und sie verhalten sich nicht alle gleich. Die beiden, die du am häufigsten verwenden wirst, sind operator[] und insert:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // erstellen oder überschreiben
    votes["alice"] = 5;              // überschreibt -> 5
    votes.insert({"bob", 2});        // fügt nur ein, wenn "bob" fehlt
    votes.insert({"bob", 99});       // ignoriert, "bob" existiert bereits

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, nicht 99
}

Der entscheidende Unterschied: operator[] überschreibt einen vorhandenen Wert, während insert einen bereits vorhandenen Schlüssel unberührt lässt. Wenn du C++17 verwendest, gibt dir insert_or_assign(key, value) die Semantik „setze dies in jedem Fall", und try_emplace(key, args...) konstruiert den Wert nur dann an Ort und Stelle, wenn der Schlüssel neu ist - praktisch für teuer zu erzeugende Werte.

Die operator[]-Falle: Es fügt beim Lesen ein

Das ist der häufigste unordered_map-Fehler, deshalb bekommt er einen eigenen Abschnitt. m[key] ist kein reiner Lesezugriff. Fehlt der Schlüssel, konstruiert er ihn standardmäßig und fügt ihn ein (ein int wird zu 0, ein string wird zu "") und gibt dann eine Referenz zurück. So lässt Code, der wie ein Nachschlagen aussieht, die map heimlich wachsen:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // Wir wollten nur "y" PRÜFEN, aber [] hat es eingefügt:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, nicht 1!
}

seen["y"] hat allein durch seine Erwähnung einen Eintrag "y" -> 0 erzeugt. Um die Zugehörigkeit zu testen, ohne die map zu verändern, verwende count (gibt 0 oder 1 zurück) oder find:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() liest sich sauberer als count()
    if (seen.contains("x")) cout << "x is here\n";
}

Faustregel: Verwende [] nur, wenn du erstellen oder aktualisieren willst. Für reine Lesezugriffe verwende count, contains (C++20) oder find.

find und at: Sichere Zugriffe

find gibt einen Iterator auf den Eintrag zurück oder end(), wenn der Schlüssel fehlt. Es fügt niemals ein und lässt dich in einem einzigen Zugriff sowohl auf den Schlüssel als auch auf den Wert über it->first und it->second zugreifen:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Wenn du weißt, dass der Schlüssel existieren sollte, und ein klares Scheitern willst, falls nicht, verwende at. Anders als [] fügt at nicht ein - es wirft std::out_of_range für einen fehlenden Schlüssel:

int p = prices.at("pen");   // in Ordnung
int q = prices.at("hat");   // wirft std::out_of_range - Schlüssel fehlt

Du hast also drei Zugriffsstile: [] (fügt ein), at (wirft) und find/count (melden die Anwesenheit, ohne die map anzufassen). Wähle den, dessen Fehlerverhalten zu deiner Absicht passt.

Iterieren und Löschen

Eine bereichsbasierte for-Schleife mit Structured Bindings ist der saubere Weg, jeden Eintrag zu durchlaufen. Denk daran, dass die Reihenfolge beliebig ist - verlass dich niemals darauf:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // die Reihenfolge ist nicht festgelegt
    }
}

Um einen Eintrag zu entfernen, nimmt erase direkt einen Schlüssel entgegen und gibt zurück, wie viele entfernt wurden (0 oder 1). Eine wichtige Falle: Das Löschen während der Iteration macht in einer unordered_map nur den Iterator des gelöschten Elements ungültig, verwende also den Rückgabewert von erase(it), um sicher weiterzugehen:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Entferne jedes Team mit einer Punktzahl unter 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase gibt den nächsten gültigen Iterator zurück
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Den Stil wins.erase(it++) zu schreiben oder nach einem schlichten erase(it) ein ++it zu machen, ist die klassische Falle des ungültigen Iterators - der gelöschte Iterator ist tot, nimm also immer den von erase zurückgegebenen Iterator.

map oder unordered_map?

Beide speichern Schlüssel-Wert-Paare mit einer ähnlichen API, daher hängt die Wahl davon ab, was du brauchst:

// std::map            -> sortierte Schlüssel, O(log n), Bereichsabfragen (lower_bound)
// std::unordered_map  -> keine Reihenfolge,   O(1) Durchschn., schnellstes einfaches Nachschlagen

Greife zu unordered_map, wenn du nur schnelles Nachschlagen per Schlüssel brauchst und die Reihenfolge irrelevant ist (Worthäufigkeiten zählen, Caching, Deduplizierung). Wähle map, wenn du die Schlüssel in sortierter Reihenfolge brauchst, in Reihenfolge iterieren oder Bereichsabfragen machen willst. Zwei Vorbehalte bei unordered_map: Sein O(1) ist ein Durchschnitt - ein schlechter Hash kann es verschlechtern - und ein benutzerdefinierter Schlüsseltyp braucht eine Hash-Spezialisierung oder einen Hash-Funktor, während map nur operator< benötigt.

Als Nächstes: Set

Du hast nun beide Varianten von Schlüssel-Wert-Containern gesehen. Manchmal brauchst du jedoch überhaupt keinen Wert - es interessiert dich nur, ob etwas vorhanden ist, etwa eine Sammlung eindeutiger Tags oder besuchter IDs. Als Nächstes sehen wir uns std::set an (und seinen Hash-basierten Verwandten unordered_set), die nur Schlüssel speichern und sie automatisch eindeutig halten.

Häufig gestellte Fragen

Was ist der Unterschied zwischen map und unordered_map in C++?

std::map ist ein balancierter Binärbaum: Die Schlüssel bleiben sortiert und die Operationen sind O(log n). std::unordered_map ist eine Hashtabelle: Die Schlüssel haben keine bestimmte Reihenfolge, aber Einfügen und Nachschlagen sind im Durchschnitt O(1). Verwende unordered_map, wenn du nur schnelles Nachschlagen per Schlüssel brauchst und dir die Reihenfolge egal ist; verwende map, wenn du sortierte Iteration oder Bereichsabfragen brauchst.

Fügt unordered_map[] einen Schlüssel ein, wenn er nicht existiert?

Ja. m[key] konstruiert standardmäßig und fügt den Schlüssel ein, wenn er fehlt, und gibt dann eine Referenz darauf zurück. Das bedeutet, dass selbst ein wie ein Lesezugriff aussehendes if (m[key] == ...) die map stillschweigend wachsen lässt. Um die Zugehörigkeit zu prüfen, ohne einzufügen, verwende stattdessen m.count(key) oder m.find(key).

Ist unordered_map in C++ immer schneller als map?

Nein. Es ist im Durchschnitt O(1), aber das Hashing hat einen Mehraufwand, und ein schlechter Hash (oder feindliche Schlüssel) kann das Nachschlagen auf O(n) verschlechtern. Bei kleinen Maps können die konstanten Faktoren und das schlechtere Cache-Verhalten eine sortierte map genauso schnell oder schneller machen. Miss nach, wenn es darauf ankommt, aber greife standardmäßig zu unordered_map, wenn du nur Nachschlagen per Schlüssel brauchst.

Verwandte Konzepte