Aký je rozdiel medzi map a unordered_map v C++?

std::map — asociačný kontajner, ktorý uchováva páry "kľúč-hodnota", zoradené podľa kľúča. Založený na červeno-čiernom strome. Čas prístupu, vkladania a mazania prvkov je logaritmický (O(log n)).

std::unordered_map — asociačný kontajner, ktorý uchováva páry "kľúč-hodnota" v hash tabuľke. Prvky nie sú zoradené. Priemerný čas prístupu, vkladania a mazania je konštantný (O(1)), ale v najhoršom prípade môže byť lineárny (O(n)) kvôli kolíziám. Vyžaduje hashovaciu funkciu pre typ kľúča a operátor rovnosti (operator==).

Charakteristika	std::map	std::unordered_map
Základ	Červeno-čierne strom	Hash tabuľka
Zoradenie prvkov	Podľa kľúča	Nie
Priemerná zložitosť operácií (prístup, vkladanie, mazanie)	O(log n)	O(1)
Najhoršia zložitosť	O(log n)	O(n) (pri kolíziách)
Požiadavky na kľúč	< operátor	Hash funkcia, == operátor
Pamäťová náročnosť	Viac	Menej (v priemere, môže sa líšiť)

Príklad použitia:

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

int main() {
    // Použitie std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Prvky sú zoradené podľa kľúča (apple, banana, orange)

    // Použitie 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;
    // Prvky nie sú zoradené
    
    return 0;
}