Uit welke standaardcontainer is de datastructuur map geïmplementeerd?

In de standaardbibliotheek van C++ is de datastructuur std::map geïmplementeerd op basis van rood-zwart boom (Red-Black Tree). Het is een gebalanceerde binaire zoekboom die logaritmische tijden garandeert voor het invoegen, verwijderen en zoeken van elementen.

In C++ is std::map een associatieve container die paren sleutel-waarde opslaat in gesorteerde volgorde op basis van de sleutel. Dankzij de rood-zwart boom wordt de boom in balans gehouden en zijn de operaties efficiënt.

Voorbeeld van gebruik van std::map:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "een";
    myMap[2] = "twee";
    myMap[3] = "drie";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

Dus, std::map is gebaseerd op een gebalanceerde boom, niet op een hash-tabel (voor hash-tabellen wordt std::unordered_map gebruikt).