Qual è la complessità di lavorare con i contenitori map e unordered_map in C++?

std::map (Albero rosso-nero)

• Inserimento, eliminazione, ricerca: O(log N) in media e nel caso peggiore. N è il numero di elementi.
• Accesso tramite chiave usando operator[] o metodo at(): O(log N).
• Ottenere un iteratore all'inizio/fine: O(1).
• Iterare su tutti gli elementi: O(N).
• Memoria: O(N).

std::unordered_map (Tabella hash)

• Inserimento, eliminazione, ricerca: O(1) in media. O(N) nel caso peggiore (quando ci sono collisioni forti dell'hash). N è il numero di elementi.
• Accesso tramite chiave usando operator[] o metodo at(): O(1) in media. O(N) nel caso peggiore.
• Ottenere un iteratore all'inizio/fine: O(1).
• Iterare su tutti gli elementi: O(N) in media. L'ordine di iterazione non è garantito.
• Memoria: O(N). Dipende dal fattore di carico e dall'implementazione della tabella hash.

Confronto:

Operazione	std::map (O)	std::unordered_map (O)
Inserimento, Eliminazione	log N	1 (media), N (peggiore)
Ricerca	log N	1 (media), N (peggiore)
Accesso tramite chiave	log N	1 (media), N (peggiore)
Iterare su tutti gli elementi	N	N (media)

std::unordered_map è generalmente più veloce per operazioni singole (inserimento, ricerca, eliminazione) grazie a O(1) in media, ma richiede una buona funzione hash ed è sensibile alle collisioni. std::map garantisce una complessità logaritmica indipendentemente dai dati, mantiene gli elementi ordinati e non richiede una funzione hash per il tipo di chiave.