Qual é a complexidade de trabalhar com os contêineres map e unordered_map em C++?

std::map (Árvore vermelho-preto)

• Inserção, remoção, busca: O(log N) em média e no pior caso. N é a quantidade de elementos.
• Acesso por chave usando operator[] ou método at(): O(log N).
• Obter iterador para o início/fim: O(1).
• Iterar sobre todos os elementos: O(N).
• Memória: O(N).

std::unordered_map (Tabela de dispersão)

• Inserção, remoção, busca: O(1) em média. O(N) no pior caso (quando há colisões fortes na hash). N é a quantidade de elementos.
• Acesso por chave usando operator[] ou método at(): O(1) em média. O(N) no pior caso.
• Obter iterador para o início/fim: O(1).
• Iterar sobre todos os elementos: O(N) em média. A ordem de iteração não é garantida.
• Memória: O(N). Depende do fator de carga e da implementação da tabela de dispersão.

Comparação:

Operação	std::map (O)	std::unordered_map (O)
Inserção, Remoção	log N	1 (média), N (pior)
Busca	log N	1 (média), N (pior)
Acesso por chave	log N	1 (média), N (pior)
Iteração sobre todos	N	N (média)

std::unordered_map geralmente é mais rápido para operações individuais (inserção, busca, remoção) devido a O(1) em média, mas requer uma boa função hash e é sensível a colisões. std::map garante complexidade logarítmica independentemente dos dados, mantém os elementos ordenados e não requer uma função hash para o tipo de chave.