Care este diferența dintre map și unordered_map în C++?

std::map — un container asociativ care stochează perechi de tip "cheie-valoare", sortate după cheie. Bazat pe un arbore roșu-negru. Timpul de accesare, inserare și ștergere a elementelor este logaritmic (O(log n)).

std::unordered_map — un container asociativ care stochează perechi de tip "cheie-valoare" într-un tabel hash. Elementele nu sunt sortate. În medie, timpul de acces, inserare și ștergere a elementelor este constant (O(1)), dar în cel mai rău caz poate fi liniar (O(n)) din cauza coliziunilor. Necesită o funcție hash pentru tipul cheii și un operator de comparație pentru egalitate (operator==).

Caracteristici	std::map	std::unordered_map
Bază	Arbore roșu-negru	Tabel hash
Sortarea elementelor	După cheie	Nu
Complexitatea medie a operațiilor (acces, inserare, ștergere)	O(log n)	O(1)
Complexitatea în cel mai rău caz (acces, inserare, ștergere)	O(log n)	O(n) (în coliziuni)
Cerințe pentru cheie	Operatorul <	Funcție hash, operatorul ==
Consumul de memorie	Mai mult	Mai puțin (în medie, poate varia)

Exemplu de utilizare:

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

int main() {
    // Utilizare std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Elementele sunt stocate în ordine sortată după cheie (apple, banana, orange)

    // Utilizare 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;
    // Elementele sunt stocate fără o ordine specifică
    
    return 0;
}