¿Cuál es la complejidad de trabajar con los contenedores map y unordered_map en C++?

std::map (Árbol rojo-negro)

• Inserción, eliminación, búsqueda: O(log N) en promedio y en el peor de los casos. N es la cantidad de elementos.
• Acceso por clave usando operator[] o método at(): O(log N).
• Obtener iterador al principio/final: O(1).
• Iterar sobre todos los elementos: O(N).
• Memoria: O(N).

std::unordered_map (Tabla hash)

• Inserción, eliminación, búsqueda: O(1) en promedio. O(N) en el peor de los casos (cuando hay colisiones fuertes en el hash). N es la cantidad de elementos.
• Acceso por clave usando operator[] o método at(): O(1) en promedio. O(N) en el peor de los casos.
• Obtener iterador al principio/final: O(1).
• Iterar sobre todos los elementos: O(N) en promedio. El orden de iteración no está garantizado.
• Memoria: O(N). Depende del factor de carga y la implementación de la tabla hash.

Comparación:

Operación	std::map (O)	std::unordered_map (O)
Inserción, Eliminación	log N	1 (promedio), N (peor)
Búsqueda	log N	1 (promedio), N (peor)
Acceso por clave	log N	1 (promedio), N (peor)
Iterar sobre todos	N	N (promedio)

std::unordered_map suele ser más rápido para operaciones individuales (inserción, búsqueda, eliminación) gracias a O(1) en promedio, pero requiere una buena función hash y es sensible a las colisiones. std::map garantiza una complejidad logarítmica independientemente de los datos, mantiene los elementos en orden ordenado y no requiere una función hash para el tipo de clave.