C++ std::map: Schlüssel, Werte, Suche und Einfügen

Dinge per Schlüssel nachschlagen

Ein vector ist großartig, wenn du nach Position indizierst – Element 0, Element 1 und so weiter. Aber oft hast du keine Position; du hast einen Namen und willst das, was daran hängt: ein Benutzer und seine Punktzahl, ein Wort und seine Häufigkeit, ein Ländercode und seine Hauptstadt. Einen vector zu durchsuchen, um eine Übereinstimmung zu finden, ist O(n) und wird schnell langsam.

std::map löst das. Sie speichert Schlüssel-Wert-Paare, hält sie nach Schlüssel sortiert und lässt dich einen Wert über seinen Schlüssel in O(log n) nachschlagen. Binde <map> ein, um sie zu nutzen:

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> liest sich als „eine map von string-Schlüsseln zu int-Werten". Schlüssel sind eindeutig – weist du demselben Schlüssel zweimal zu, gewinnt der zweite Wert. Intern ist eine map ein balancierter binärer Suchbaum, weshalb alles sortiert bleibt und Suchen logarithmisch statt konstant sind.

Elemente einfügen

Es gibt mehrere Wege, Einträge hinzuzufügen, und der Unterschied zwischen ihnen ist wichtig. Am gängigsten ist operator[], der den Schlüssel anlegt, falls er nicht existiert, und eine Referenz zurückgibt, der du zuweisen kannst:

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // anlegen + zuweisen
    inventory["apples"] += 3;     // lesen-ändern-schreiben, jetzt 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Willst du ein Einfügen, das sich weigert, einen vorhandenen Schlüssel zu überschreiben, verwende insert oder emplace. Beide geben ein pair zurück, dessen .second ein bool ist und dir mitteilt, ob das Einfügen tatsächlich stattgefunden hat:

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada existiert bereits
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, unverändert
}

Verwende [], wenn „der letzte Schreibvorgang gewinnt" gewünscht ist, und insert/emplace, wenn ein vorhandener Schlüssel in Ruhe gelassen werden soll.

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

Das ist der mit Abstand häufigste map-Fehler. operator[] ist kein reines Lesen – fehlt der Schlüssel, legt er ihn stillschweigend mit einem standardkonstruierten Wert an (0 für int, "" für string usw.) und gibt eine Referenz darauf zurück. Allein das Prüfen eines Schlüssels mit [] verändert also die map:

map<string, int> m;
if (m["maybe"] == 0) {   // BUG: das hat gerade "maybe" -> 0 erzeugt
    // ...
}
cout << m.size();        // 1, nicht 0 - du hast aus Versehen einen Schlüssel eingefügt

Das beißt dich auch bei einer const map, wo operator[] nicht einmal kompiliert, weil er eventuell einfügen müsste. Um zu lesen, ohne einzufügen, verwende find, count/contains oder at:

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: gibt einen Iterator zurück, == end() falls nicht vorhanden
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) oder count (jede Version)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: wirft std::out_of_range, falls nicht vorhanden - fügt nie ein
    cout << "a = " << m.at("a") << "\n";
}

Faustregel: Willst du lesen, greife nie zu []. Verwende at, wenn der Schlüssel existieren muss, und find/contains, wenn er vielleicht nicht existiert.

In sortierter Reihenfolge iterieren

Da eine map baumbasiert ist, besucht das Iterieren die Schlüssel in aufsteigender sortierter Reihenfolge – immer und gratis. Jedes Element ist ein pair<const Key, Value>, also nutze eine strukturierte Bindung, um Schlüssel und Wert sauber zu entpacken:

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // fehlende Schlüssel starten bei 0, dann ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Beachte, dass der Schlüssel in der Bindung const ist – du kannst einen Wert in der Schleife mit auto& ändern, aber niemals einen Schlüssel an Ort und Stelle (das würde die Sortierreihenfolge zerstören). Die Ausgabe kommt alphabetisch (blue, sea, sky) ohne irgendeinen Sortierschritt heraus, was genau der Grund ist, warum man map einer Hashtabelle vorzieht, wenn geordnetes Durchlaufen zählt.

Das wordCount[w]++-Idiom ist auch die kanonische Nutzung des Einfügens-beim-Zugriff: Hier willst du, dass ein fehlender Schlüssel bei 0 startet, also ist [] das richtige Werkzeug.

Elemente entfernen und Größe ermitteln

Lösche per Schlüssel mit erase, was zurückgibt, wie viele Elemente entfernt wurden (0 oder 1 bei einer map). Du kannst auch über einen Iterator von find löschen. Prüfe den Zustand des Containers mit size() und empty():

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (war nicht da)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Eine Falle beim Löschen innerhalb einer Schleife: m.erase(it) macht it ungültig, du kannst danach also kein ++it ausführen. Das sichere Muster seit C++11 ist it = m.erase(it), das einen Iterator auf das nächste Element zurückgibt. Für ein einmaliges bedingtes Entfernen über die gesamte map ist std::erase_if(m, predicate) (C++20) sauberer.

Als Nächstes: unordered_map

std::map gibt dir sortierte Schlüssel und vorhersehbare O(log n)-Operationen, aber diese Ordnung bezahlst du bei jeder Suche. Wenn dir die Schlüsselreihenfolge egal ist und du einfach die schnellstmöglichen Suchen willst, tauscht unordered_map den sortierten Baum gegen eine Hashtabelle – im Durchschnitt O(1)-Zugriff. Als Nächstes sehen wir, wie sie funktioniert, wann ihre durchschnittlich konstante Zeit den Logarithmus der map schlägt und welche Hashing-Fallstricke (eigene Schlüsseltypen, Worst-Case-Kollisionen) damit einhergehen.