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

Der Hauptunterschied liegt darin, wie Elemente gespeichert und abgerufen werden:

• std::map: Speichert Elemente in sortierter Reihenfolge nach Schlüssel. Wird in der Regel auf Basis eines Rot-Schwarz-Baums implementiert. Suche, Einfügen und Löschen haben eine logarithmische Komplexität O(log N), wobei N die Anzahl der Elemente ist.
• std::unordered_map: Speichert Elemente in einer Hashtabelle. Die Reihenfolge der Elemente ist beliebig. Im Durchschnitt haben Suche, Einfügen und Löschen eine konstante Komplexität O(1). Im schlimmsten Fall, bei Kollisionen, kann die Komplexität O(N) erreichen.

Merkmal	std::map	std::unordered_map
Sortierung	Nach Schlüssel (aufsteigend)	Nein
Grundstruktur	Rot-Schwarz-Baum	Hashtabelle
Durchschnittliche Komplexität	O(log N)	O(1)
Schlimmer Fall	O(log N)	O(N)
Anforderungen an Schlüssel	Operator <	Hash-Funktion und ==

Beispiel für die Verwendung:

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

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

    // Ausgabe: apple 1, banana 3, cherry 2 (Reihenfolge ist wichtig)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    std::cout << "---" << std::endl;

    // std::unordered_map: Reihenfolge der Elemente ist nicht garantiert
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Die Ausgabe kann variieren (z.B. cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}