De que contêiner padrão a estrutura de dados map é implementada?

Na biblioteca padrão do C++, a estrutura de dados std::map é implementada com base em árvore vermelho-preto (Red-Black Tree). É uma árvore binária de busca balanceada que garante tempos logarítmicos para inserção, remoção e busca de elementos.

Em C++, std::map é um contêiner associativo que armazena pares chave-valor em ordem ordenada pela chave. Graças à árvore vermelho-preto, o balanceamento da árvore é garantido e as operações são eficientes.

Exemplo de uso de std::map:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "um";
    myMap[2] = "dois";
    myMap[3] = "três";

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

Portanto, std::map é baseado em uma árvore balanceada, e não em uma tabela hash (para tabelas hash, usa-se std::unordered_map).