Qual è la differenza tra i contenitori map e unordered_map in C++?

La principale differenza riguarda come gli elementi vengono memorizzati e recuperati:

• std::map: Memorizza gli elementi in ordine ordinato per chiave. Viene generalmente implementato su un albero rosso-nero. La ricerca, l'inserimento e la rimozione hanno una complessità logaritmica O(log N), dove N è il numero di elementi.
• std::unordered_map: Memorizza gli elementi in una tabella hash. L'ordine degli elementi è arbitrario. In media, la ricerca, l'inserimento e la rimozione hanno una complessità costante O(1). Nel caso peggiore, con collisioni, la complessità può raggiungere O(N).

Caratteristica	std::map	std::unordered_map
Ordinamento	Per chiave (crescendo)	No
Struttura di base	Albero rosso-nero	Tabella hash
Complessità media	O(log N)	O(1)
Caso peggiore	O(log N)	O(N)
Requisiti chiave	Operatore <	Funzione hash e ==

Esempio di utilizzo:

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

int main() {
    // std::map: elementi ordinati per chiave
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Output: apple 1, banana 3, cherry 2 (l'ordine è importante)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

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

    // std::unordered_map: ordine degli elementi non garantito
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // L'output può variare (ad esempio, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}