Qual é a diferença entre os contêineres map e unordered_map em C++?

A principal diferença reside na forma como os elementos são armazenados e recuperados:

• std::map: Armazena os elementos em ordem classificada por chave. Geralmente é implementado com uma árvore vermelho-preto. A busca, inserção e remoção têm uma complexidade logarítmica O(log N), onde N é a quantidade de elementos.
• std::unordered_map: Armazena os elementos numa tabela de dispersão. A ordem dos elementos é arbitrária. Em média, busca, inserção e remoção têm uma complexidade constante O(1). No pior caso, com colisões, a complexidade pode atingir O(N).

Característica	std::map	std::unordered_map
Ordenação	Por chave (ascendente)	Não
Estrutura base	Árvore vermelho-preto	Tabela de dispersão
Complexidade média	O(log N)	O(1)
Pior caso	O(log N)	O(N)
Requisitos de chave	Operador <	Função hash e ==

Exemplo de uso:

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

int main() {
    // std::map: elementos ordenados por chave
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Saída: apple 1, banana 3, cherry 2 (a ordem importa)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    std::cout << "---" << std::endl;

    // std::unordered_map: ordem dos elementos não garantida
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // A saída pode variar (por exemplo, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}