Iz kojeg standardnog kontejnera je implementirana struktura podataka map?

U standardnoj biblioteci C++, struktura podataka std::map implementirana je na osnovu crveno-crnog stabla (Red-Black Tree). To je uravnoteženo binarno pretraživačko stablo koje obezbeđuje logaritamsko vreme za umetanje, brisanje i pretraživanje elemenata.

U C++, std::map je asocijativni kontejner koji čuva parove ključ-vrednost u sortiranoj formi po ključu. Zahvaljujući crveno-crnom stablu, stablo je uravnoteženo i operacije su efikasne.

Primer korišćenja std::map:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "jedan";
    myMap[2] = "dva";
    myMap[3] = "tri";

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

Dakle, std::map se zasniva na uravnoteženom stablu, a ne na hash tabeli (za hash tabele koristi se std::unordered_map).