Qual é a diferença entre map e unordered_map em C++?

std::map — um contêiner associativo que armazena pares de "chave-valor", ordenados por chave. Baseado em uma árvore vermelho-preto. O tempo de acesso, inserção e remoção de elementos é logarítmico (O(log n)).

std::unordered_map — um contêiner associativo que armazena pares de "chave-valor" em uma tabela hash. Os elementos não são ordenados. Em média, o tempo de acesso, inserção e remoção de elementos é constante (O(1)), mas no pior caso pode ser linear (O(n)) devido a colisões. Requer uma função hash para o tipo de chave e um operador de comparação de igualdade (operator==).

Característica	std::map	std::unordered_map
Base	Árvore vermelho-preto	Tabela hash
Ordenação de elementos	Por chave	Não
Complexidade média de operações (acesso, inserção, remoção)	O(log n)	O(1)
Complexidade no pior caso (acesso, inserção, remoção)	O(log n)	O(n) (em colisões)
Requisitos para a chave	< operador	Função hash, == operador
Consumo de memória	Maior	Menor (em média, mas pode variar)

Exemplo de uso:

#include <map>
#include <unordered_map>
#include <string>

int main() {
    // Uso de std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Os elementos são armazenados em ordem ordenada por chave (apple, banana, orange)

    // Uso de std::unordered_map
    std::unordered_map<std::string, int> my_unordered_map;
    my_unordered_map["apple"] = 1;
    my_unordered_map["banana"] = 2;
    my_unordered_map["orange"] = 3;
    // Os elementos são armazenados sem uma ordem definida
    
    return 0;
}