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

Het belangrijkste verschil ligt in hoe de elementen worden opgeslagen en opgehaald:

• std::map: Slaat de elementen op in gesorteerde volgorde op basis van de sleutel. Wordt meestal geïmplementeerd op basis van een rood-zwart boom. Zoeken, invoegen en verwijderen hebben een logaritmische complexiteit O(log N), waarbij N het aantal elementen is.
• std::unordered_map: Slaat de elementen op in een hash-tabel. De volgorde van de elementen is willekeurig. Gemiddeld hebben zoeken, invoegen en verwijderen een constante complexiteit O(1). In het slechtste geval, bij collisions, kan de complexiteit O(N) worden.

Kenmerk	std::map	std::unordered_map
Sortering	Op sleutel (stijgend)	Nee
Basisstructuur	Rood-zwart boom	Hash-tabel
Gemiddelde complexiteit	O(log N)	O(1)
Worst case	O(log N)	O(N)
Vereisten voor sleutel	Operator <	Hash-functie en ==

Voorbeeld van gebruik:

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

int main() {
    // std::map: elementen gesorteerd op sleutel
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Uitvoer: apple 1, banana 3, cherry 2 (volgorde is belangrijk)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

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

    // std::unordered_map: volgorde van elementen niet gegarandeerd
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // De uitvoer kan variëren (bijvoorbeeld, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}