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

std::map — ein assoziativer Container, der Paare "Schlüssel-Wert" speichert, sortiert nach dem Schlüssel. Basierend auf einem Rot-Schwarz-Baum. Die Zugriffs-, Einfüge- und Löschzeiten sind logarithmisch (O(log n)).

std::unordered_map — ein assoziativer Container, der Paare "Schlüssel-Wert" in einer Hash-Tabelle speichert. Die Elemente sind nicht sortiert. Im Durchschnitt sind Zugriffs-, Einfüge- und Löschzeiten konstant (O(1)), im schlimmsten Fall können sie linear (O(n)) sein, bei Kollisionen. Erfordert eine Hash-Funktion für den Schlüsseltyp und einen Gleichheitsoperator (operator==).

Eigenschaft	std::map	std::unordered_map
Grundlage	Rot-Schwarz-Baum	Hash-Tabelle
Sortierung der Elemente	Nach Schlüssel	Keine
Durchschnittliche Komplexität	O(log n)	O(1)
Schlechteste Komplexität	O(log n)	O(n) (bei Kollisionen)
Anforderungen an den Schlüssel	< Operator	Hash-Funktion, == Operator
Speicherverbrauch	Mehr	Weniger (im Durchschnitt, kann variieren)

Beispiel für die Verwendung:

#include <map>
#include <unordered_map>
#include <string>

int main() {
    // Verwendung von std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Elemente sind sortiert nach Schlüssel (apple, banana, orange)

    // Verwendung von std::unordered_map
    std::unordered_map<std::string, int> my_unordered_map;
    my_unordered_map["apple"] = 1;
    my_unordered_map["banana"] = 2;
    my_unordered_map["orange"] = 3;
    // Elemente sind ungeordnet
    
    return 0;
}