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

Principala diferență constă în modul în care sunt stocate și recuperate elementele:

• std::map: Stochează elementele în ordine sortată după cheie. De obicei, este implementată pe baza unui arbore roșu-negru. Căutarea, inserarea și ștergerea au o complexitate logaritmică O(log N), unde N este numărul de elemente.
• std::unordered_map: Stochează elementele într-un tabel hash. Ordinea elementelor este arbitrară. În medie, căutarea, inserarea și ștergerea au o complexitate constantă O(1). În cel mai rău caz, cu coliziuni, complexitatea poate ajunge la O(N).

Caracteristică	std::map	std::unordered_map
Ordine	Pe cheie (crescendo)	Nu
Structură de bază	Arbore roșu-negru	Tabel hash
Complexitate medie	O(log N)	O(1)
Cazul cel mai rău	O(log N)	O(N)
Cerințe pentru cheie	Operator <	Funcție hash și ==

Exemplu de utilizare:

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

int main() {
    // std::map: elemente sortate după cheie
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Ieșire: apple 1, banana 3, cherry 2 (ordinea contează)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

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

    // std::unordered_map: ordinea elementelor nu este garantată
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Ieșirea poate varia (de exemplu, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}