Mi a különbség a map és az unordered_map konténerek között C++-ban?

A fő különbség abban rejlik, hogy hogyan tárolódnak és kerülnek előhívásra az elemek:

• std::map: Az elemeket kulcs szerint rendezett sorrendben tárolja. Általában egy piros-fekete fa alapú megvalósítás. A keresés, beszúrás és törlés logaritmikus komplexitású O(log N), ahol N az elemek száma.
• std::unordered_map: Az elemeket egy hash-táblában tárolja. Az elemek sorrendje véletlenszerű. Átlagosan a keresés, beszúrás és törlés állandó komplexitású O(1). Legrosszabb esetben, ütközések esetén, a komplexitás elérheti az O(N)-t.

Jellemző	std::map	std::unordered_map
Rendezés	Kulcs szerint (növekvő)	Nem
Alapstruktúra	Piros-fekete fa	Hash-tábla
Átlagos komplexitás	O(log N)	O(1)
Legrosszabb eset	O(log N)	O(N)
Kulcs követelmények	< operátor	Hash függvény és ==

Használati példa:

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

int main() {
    // std::map: elemek rendezve kulcs szerint
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Kimenet: apple 1, banana 3, cherry 2 (a sorrend számít)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

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

    // std::unordered_map: a elemek sorrendje nem garantált
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // A kimenet változhat (pl. cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}