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

Hlavný rozdiel spočíva v tom, ako sú prvky uložené a načítané:

• std::map: Ukladá prvky v zoradenom poradí podľa kľúča. Zvyčajne je implementovaná na základe červeno-čierneho stromu. Vyhľadávanie, vkladanie a odstraňovanie majú logaritmickú zložitosť O(log N), kde N je počet prvkov.
• std::unordered_map: Ukladá prvky v hash tabuľke. Poradie prvkov je ľubovoľné. Priemerná zložitosť vyhľadávania, vkladania a odstraňovania je konštantná O(1). V najhoršom prípade, pri kolíziách, môže dosiahnuť zložitosť O(N).

Vlastnosť	std::map	std::unordered_map
Zoradenie	Podľa kľúča (rastúce)	Nie
Základná štruktúra	Červeno-čierny strom	Hash tabuľka
Priemerná zložitosť	O(log N)	O(1)
Najhorší prípad	O(log N)	O(N)
Požiadavky na kľúč	Operátor <	Hash funkcia a ==

Príklad použitia:

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

int main() {
    // std::map: prvky zoradené podľa kľúča
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Výstup: apple 1, banana 3, cherry 2 (poradie je dôležité)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

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

    // std::unordered_map: poradie prvkov nie je garantované
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Výstup sa môže líšiť (napríklad, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}