Kokio standarto konteineryje įgyvendinta duomenų struktūra map?

C++ standartinėje bibliotekos struktūroje std::map yra įgyvendinta remiantis raudonai-juodu medžiu (Red-Black Tree). Tai subalansuotas dvejopo paieškos medis, kuris užtikrina logaritminį laiką elementų įterpimui, šalinimui ir paieškai.

C++ kalboje std::map yra asociatyvinis konteineris, kuris saugo poras raktas-reikšmė išrikiuotas pagal raktą. Dėka raudonai-juodo medžio, medis yra subalansuotas, o operacijos efektyvios.

std::map naudojimo pavyzdys:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "vienas";
    myMap[2] = "du";
    myMap[3] = "trys";

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

Todėl std::map yra pagrįstas subalansuotu medžiu, o ne maišos lentele (maišos lentelėms naudojama std::unordered_map).