Jaký je rozdíl mezi kontejnery map a unordered_map v C++?

Hlavní rozdíl spočívá v tom, jak jsou prvky ukládány a načítány:

• std::map: Ukládá prvky v seřazeném pořadí podle klíče. Obvykle je implementováno na základě červené-černé stromové struktury. Vyhledávání, vkládání a mazání mají logaritmickou složitost O(log N), kde N je počet prvků.
• std::unordered_map: Ukládá prvky v hash tabulce. Pořadí prvků je libovolné. Průměrná složitost vyhledávání, vkládání a mazání je konstantní O(1). V nejhorším případě, při kolizích, může složitost dosáhnout O(N).

Vlastnost	std::map	std::unordered_map
Seřazení	Podle klíče (vzestupně)	Ne
Základní struktura	Červená-černá strom	Hash tabulka
Průměrná složitost	O(log N)	O(1)
Nejhorší případ	O(log N)	O(N)
Požadavky na klíč	Operátor <	Hash funkce a ==

Příklad použití:

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

int main() {
    // std::map: prvky seřazeny podle klíče
    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 (pořadí 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: pořadí prvků není garantováno
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Výstup se může lišit (například cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}