Mis vahe on map ja unordered_map konteineritel C++-s?

Peamine erinevus seisneb selles, kuidas elemendid salvestatakse ja välja võetakse:

• std::map: Salvestab elemendid võtme järgi sorteeritud järjekorras. Tavaliselt on see realiseeritud punase-musta puu alusel. Otsing, lisamine ja kustutamine on logaritmilise keerukusega O(log N), kus N on elementide arv.
• std::unordered_map: Salvestab elemendid hajutatud tabelis. Järjekord on juhuslik. Keskmiselt on otsing, lisamine ja kustutamine konstantse keerukusega O(1). Halvimal juhul, kokkulangevuste tõttu, võib keerukus ulatuda O(N)-ni.

Näitaja	std::map	std::unordered_map
Järjekord	Võtme järgi (kasvav)	Ei ole
Põhistruktuur	Punase-musta puu	Hajutatud tabel
Keskmine keerukus	O(log N)	O(1)
Halvim keerukus	O(log N)	O(N)
Võtme nõuded	< operaator	Hash-funktsioon ja ==

Näide kasutamiseks:

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

int peamine() {
    // std::map: elemendid on sorteeritud võtme järgi
    std::map<std::string, int> sorteeritud_map;
    sorteeritud_map["banaan"] = 3;
    sorteeritud_map["õun"] = 1;
    sorteeritud_map["kirss"] = 2;

    // Väljund: õun 1, banaan 3, kirss 2 (järjekord on oluline)
    for (const auto& paar : sorteeritud_map) {
        std::cout << paar.first << " " << paar.second << std::endl;
    }

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

    // std::unordered_map: elementide järjekord ei ole garanteeritud
    std::unordered_map<std::string, int> vaba_map;
    vaba_map["banaan"] = 3;
    vaba_map["õun"] = 1;
    vaba_map["kirss"] = 2;

    // Väljund võib olla erinev (näiteks kirss 2, õun 1, banaan 3)
    for (const auto& paar : vaba_map) {
        std::cout << paar.first << " " << paar.second << std::endl;
    }

    return 0;
}