Wat is het verschil tussen map en unordered_map in C++?

std::map — een associatieve container die paren "sleutel-waarde" opslaat, gesorteerd op de sleutel. Gebaseerd op een rode-zwart boom. Toegangs-, invoeg- en verwijderingstijd is logaritmisch (O(log n)).

std::unordered_map — een associatieve container die paren "sleutel-waarde" opslaat in een hash-tabel. De elementen zijn niet gesorteerd. Gemiddeld is de toegang, invoeging en verwijderingstijd constant (O(1)), maar in het slechtste geval kan het lineair (O(n)) zijn door collisions. Vereist een hash-functie voor het sleuteltype en een gelijkheid operator (operator==).

Kenmerk	std::map	std::unordered_map
Basis	Rode-zwart boom	Hash-tabel
Sortering van elementen	Op sleutel	Geen
Gemiddelde complexiteit van operaties (toegang, invoegen, verwijderen)	O(log n)	O(1)
Slechtste complexiteit	O(log n)	O(n) (bij collisions)
Vereisten voor de sleutel	< operator	Hash-functie, == operator
Geheugengebruik	Meer	Minder (gemiddeld, kan variëren)

Voorbeeld van gebruik:

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

int main() {
    // Gebruik van std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Elementen worden gesorteerd opgeslagen op sleutel (apple, banana, orange)

    // Gebruik van 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;
    // Elementen worden niet gesorteerd opgeslagen
    
    return 0;
}