Kuo skiriasi map ir unordered_map konteineriai C++?

Pagrindinis skirtumas yra tai, kaip elementai yra saugomi ir išgaunami:

• std::map: Saugo elementus pagal raktą surūšiuotu būdu. Paprastai įgyvendinama remiantis raudonai-juoda medžiu. Paieška, įterpimas ir ištrynimas turi logaritminį sudėtingumą O(log N), kur N yra elementų skaičius.
• std::unordered_map: Saugo elementus maišos lentelėje. Tvarka yra atsitiktinė. Vidutiniškai, paieška, įterpimas ir ištrynimas turi pastovų sudėtingumą O(1). Blogiausiu atveju, esant kolizijoms, sudėtingumas gali siekti O(N).

Žymuo	std::map	std::unordered_map
Tvarka	Pagal raktą (auganti)	Nėra
Pagrindinė struktūra	Raudonai-juoda medžio struktūra	Maišos lentelė
Vidutinis sudėtingumas	O(log N)	O(1)
Blogiausias atvejis	O(log N)	O(N)
Raktų reikalavimai	Operatorius <	Maišos funkcija ir ==

Pavyzdys naudojimui:

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

int main() {
    // std::map: elementai surūšiuoti pagal raktą
    std::map<std::string, int> surūšiuotas_map;
    surūšiuotas_map["bananas"] = 3;
    surūšiuotas_map["obuolys"] = 1;
    surūšiuotas_map["vyšnia"] = 2;

    // Išvedimas: obuolys 1, bananas 3, vyšnia 2 (tvarka svarbi)
    for (const auto& pora : surūšiuotas_map) {
        std::cout << pora.first << " " << pora.second << std::endl;
    }

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

    // std::unordered_map: elementų tvarka nėra garantuota
    std::unordered_map<std::string, int> laisvas_map;
    laisvas_map["bananas"] = 3;
    laisvas_map["obuolys"] = 1;
    laisvas_map["vyšnia"] = 2;

    // Išvedimas gali būti skirtingas (pavyzdžiui, vyšnia 2, obuolys 1, bananas 3)
    for (const auto& pora : laisvas_map) {
        std::cout << pora.first << " " << pora.second << std::endl;
    }

    return 0;
}