Wie ist die Komplexität bei der Arbeit mit den Containern map und unordered_map in C++?

std::map (Rot-Schwarz-Baum)

• Einfügen, Löschen, Suchen: O(log N) im Durchschnitt und im schlimmsten Fall. N ist die Anzahl der Elemente.
• Zugriff nach Schlüssel mit operator[] oder Methode at(): O(log N).
• Iterator auf Anfang/Ende: O(1).
• Iteration über alle Elemente: O(N).
• Speicher: O(N).

std::unordered_map (Hash-Tabelle)

• Einfügen, Löschen, Suchen: O(1) im Durchschnitt. O(N) im schlimmsten Fall (bei starken Kollisionen im Hash). N ist die Anzahl der Elemente.
• Zugriff nach Schlüssel mit operator[] oder Methode at(): O(1) im Durchschnitt. O(N) im schlimmsten Fall.
• Iterator auf Anfang/Ende: O(1).
• Iteration über alle Elemente: O(N) im Durchschnitt. Die Reihenfolge der Iteration ist nicht garantiert.
• Speicher: O(N). Hängt vom Ladungsfaktor und der Implementierung der Hash-Tabelle ab.

Vergleich:

Operation	std::map (O)	std::unordered_map (O)
Einfügen, Löschen	log N	1 (durchschnittlich), N (schlimmste)
Suchen	log N	1 (durchschnittlich), N (schlimmste)
Zugriff nach Schlüssel	log N	1 (durchschnittlich), N (schlimmste)
Iteration über alle	N	N (durchschnittlich)

std::unordered_map ist in der Regel schneller für einzelne Operationen (Einfügen, Suchen, Löschen) dank O(1) im Durchschnitt, erfordert jedoch eine gute Hash-Funktion und ist empfindlich gegenüber Kollisionen. std::map garantiert eine logarithmische Komplexität unabhängig von den Daten, hält die Elemente sortiert und benötigt keine Hash-Funktion für den Schlüsseltyp.