От кой стандартен контейнер е реализирана структурата данни map?

В стандартната библиотека на C++ структурата данни std::map е реализирана на базата на червено-черно дърво (Red-Black Tree). Това е балансирано двоично дърво за търсене, което осигурява логаритмично време за вмъкване, изтриване и търсене на елементи.

В C++ std::map е асоциативен контейнер, който съхранява двойки ключ-стойност в сортиран ред по ключа. Благодарение на червено-черното дърво, дървото е балансирано и операциите са ефективни.

Пример за използване на std::map:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "един";
    myMap[2] = "два";
    myMap[3] = "три";

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

Така std::map се базира на балансирано дърво, а не на хеш таблица (за хеш таблици се използва std::unordered_map).