Da quale contenitore standard è implementata la struttura dati mappa?

Nella libreria standard di C++, la struttura dati std::map è implementata su albero rosso-nero (Red-Black Tree). È un albero binario di ricerca bilanciato che garantisce tempi logaritmici per inserimento, rimozione e ricerca di elementi.

In C++, std::map è un contenitore associativo che memorizza coppie chiave-valore in ordine ordinato per chiave. Grazie all'albero rosso-nero, l'albero è bilanciato e le operazioni sono efficienti.

Esempio di utilizzo di std::map:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "uno";
    myMap[2] = "due";
    myMap[3] = "tre";

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

Pertanto, std::map si basa su un albero bilanciato, e non su una tabella hash (per le tabelle hash si utilizza std::unordered_map).