Kuo skiriasi map ir unordered_map C++?

std::map — asociatyvus konteineris, saugantis poras "raktas-reikšmė" ir išrikiuotas pagal raktą. Pagrįstas raudonai-juoda medžio struktūra. Prieigos, įterpimo ir ištrynimo laikas yra logaritminis (O(log n)).

std::unordered_map — asociatyvus konteineris, saugantis poras "raktas-reikšmė" hash lentelėje. Elementai nėra išrikiuoti. Vidutinis prieigos, įterpimo ir ištrynimo laikas yra pastovus (O(1)), bet blogiausiu atveju gali būti linijinis (O(n)) dėl kolizijų. Reikalauja hash funkcijos raktų tipui ir lyginimo operatoriaus (operator==).

Savybė	std::map	std::unordered_map
Pagrindas	Raudonai-juoda medis	Hash lentelė
Elementų rūšiavimas	Pagal raktą	Nėra
Vidutinė operacijų sudėtingumas (prieiga, įterpimas, ištrynimas)	O(log n)	O(1)
Blogiausias operacijų sudėtingumas (prieiga, įterpimas, ištrynimas)	O(log n)	O(n) (kolizijų atveju)
Raktų reikalavimai	< operatorius	Hash funkcija, == operatorius
Atminties suvartojimas	Daugiau	Mažiau (vidutiniškai, bet gali skirtis)

Pavyzdys naudojimo:

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

int main() {
    // Naudojant std::map
    std::map<std::string, int> mano_map;
    mano_map["apple"] = 1;
    mano_map["banana"] = 2;
    mano_map["orange"] = 3;
    // Elementai saugomi išrikiuoti pagal raktą (apple, banana, orange)

    // Naudojant std::unordered_map
    std::unordered_map<std::string, int> mano_neišrikiuotas_map;
    mano_neišrikiuotas_map["apple"] = 1;
    mano_neišrikiuotas_map["banana"] = 2;
    mano_neišrikiuotas_map["orange"] = 3;
    // Elementai saugomi be nustatyto tvarkos
    
    return 0;
}