¿Cuál es la diferencia entre map y unordered_map en C++?

std::map — un contenedor asociativo que almacena pares de "clave-valor", ordenados por la clave. Basado en un árbol rojo-negro. El tiempo de acceso, inserción y eliminación de elementos es logarítmico (O(log n)).

std::unordered_map — un contenedor asociativo que almacena pares de "clave-valor" en una tabla hash. Los elementos no están ordenados. En promedio, el tiempo de acceso, inserción y eliminación de elementos es constante (O(1)), pero en el peor caso puede ser lineal (O(n)) debido a colisiones. Requiere una función hash para el tipo de clave y un operador de comparación de igualdad (operator==).

Característica	std::map	std::unordered_map
Base	Árbol rojo-negro	Tabla hash
Ordenación de elementos	Por clave	No
Complejidad media de operaciones (acceso, inserción, eliminación)	O(log n)	O(1)
Complejidad en el peor caso (acceso, inserción, eliminación)	O(log n)	O(n) (en colisiones)
Requisitos para la clave	< operador	Función hash, == operador
Consumo de memoria	Mayor	Menor (en promedio, pero puede variar)

Ejemplo 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;
    // Los elementos se almacenan en orden ordenado por clave (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;
    // Los elementos se almacenan sin un orden definido
    
    return 0;
}