Z akého štandardného kontajnera je implementovaná dátová štruktúra map?

V štandardni knjižnici C++ je struktura podatkov std::map implementirana na osnovi rdeče-črnega drevesa (Red-Black Tree). To je uravnoteženo binarno iskalno drevo, ki zagotavlja logaritemski čas za vstavljanje, brisanje in iskanje elementov.

V C++ je std::map asocijativni vsebnik, ki shranjuje pare ključ-vrednost v sortirani obliki po ključu. Zahvaljujoč rdeče-črnemu drevesu je drevo uravnoteženo in operacije so učinkovite.

Primer uporabe std::map:

#include <iostream>
#include <map>

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

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

Torej, std::map temelji na uravnoteženem drevesu, ne na hashtabeli (za hashtabele se uporablja std::unordered_map).