Schlüssel-Wert-Strukturen mit std::map und std::unordered_map in C++

In C++ sind map und unordered_map die zwei wichtigsten assoziativen Container, die Schlüssel–Wert-Strukturen bereitstellen. Beide dienen dem Zweck, einen Schlüssel effizient einem zugehörigen Wert zuzuordnen, unterscheiden sich jedoch deutlich in Datenstruktur, Sortierung, Suchzeit und Leistungsmerkmalen. Dieser Artikel erklärt beide Container ausführlich und zeigt praxisnahe Beispiele.

1) Was ist map?

std::map ist ein geordneter assoziativer Container, der auf einem Rot-Schwarz-Baum (selbstbalancierender Suchbaum) basiert.

• Schlüssel werden sortiert gespeichert.
• Suchen, Einfügen und Löschen: O(log n)
• Schlüssel sind eindeutig.
• Iteration erfolgt immer in aufsteigender Schlüsselfolge.

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

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

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Hinweis: Ausgabe erfolgt alphabetisch (Alice, Bob, Charlie).

2) Was ist unordered_map?

std::unordered_map ist ein hash-basierter assoziativer Container. Er garantiert keine Sortierung, bietet jedoch extrem schnelle durchschnittliche Suchzeiten.

• Schlüssel werden gehasht → keine Reihenfolge garantiert.
• Suchen, Einfügen, Löschen: durchschnittlich O(1) (Worst Case O(n)).
• Iterationsreihenfolge ist unvorhersehbar und kann sich ändern.
• Bei großen Datenmengen meist deutlich schneller als map.

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

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

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Hinweis: Die Reihenfolge ist zufällig und kann sich bei jedem Programmstart ändern.

3) Vergleich: map vs unordered_map

Fazit: Wenn Ordnung wichtig ist → map. Wenn Geschwindigkeit wichtig ist → unordered_map.

4) Grundlegende Operationen

a) Einfügen

map<int,string> m;
m.insert({1, "One"});
m[2] = "Two";   // fügt ein oder aktualisiert

b) Suchen

auto it = m.find(1);
if (it != m.end())
    cout << "Gefunden: " << it->second;

c) Löschen

m.erase(2);          // löschen nach Schlüssel
m.erase(m.begin());  // löschen per Iterator

d) Größe & Existenzprüfung

cout << m.size();
cout << m.count(1); // 0 oder 1

5) Eigene Hash-Funktionen für unordered_map

Für eingebaute Typen (int, string, double …) existieren bereits Hash-Funktionen. Für eigene Klassen müssen Hash- und Vergleichsoperatoren definiert werden.

#include <unordered_map>
#include <string>

struct User {
    string name;
    int id;
};

struct UserHash {
    size_t operator()(User const& u) const noexcept {
        return hash<string>{}(u.name) ^ hash<int>{}(u.id);
    }
};

struct UserEq {
    bool operator()(User const& a, User const& b) const noexcept {
        return a.id == b.id && a.name == b.name;
    }
};

int main() {
    unordered_map<User, int, UserHash, UserEq> users;
}

6) Buckets & Load-Factor in unordered_map

Ein unordered_map speichert Elemente in sogenannten Buckets. Schlüssel mit gleichem Hash-Wert landen im selben Bucket (Kollision).

unordered_map<int,string> um;

cout << um.bucket_count() << endl;
cout << um.load_factor() << endl;

Steigt der Load-Factor, sinkt die Performance. Mit rehash(n) kann die Bucket-Anzahl erhöht und die Geschwindigkeit verbessert werden.

7) Praxisbeispiel – Notensystem für Studenten

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

int main() {
    unordered_map<string, double> grades;

    grades["Anna"] = 85.5;
    grades["Lukas"] = 92.0;
    grades["Johannes"] = 78.0;

    if (grades.contains("Lukas"))
        cout << "Note von Lukas: " << grades["Lukas"] << endl;

    grades.erase("Johannes");

    for (auto& g : grades)
        cout << g.first << ": " << g.second << endl;
}

8) Welche Struktur sollte verwendet werden?

• map → wenn Sortierung erforderlich ist, oder bei kleinen/mittleren Daten.
• unordered_map → wenn maximale Geschwindigkeit beim Suchen/Einfügen/Löschen benötigt wird.
• Bereichsabfragen (lower_bound, upper_bound) funktionieren nur mit map.
• Bei sehr großen Datensätzen ist unordered_map meist deutlich schneller.

Allgemeine Empfehlung: Wenn keine Sortierung nötig ist → unordered_map. Wenn geordnete Iteration benötigt wird → map.

9) TL;DR

Ähnliche Artikel