Kokia yra sudėtingumas dirbant su map ir unordered_map konteineriais C++?

std::map (Raudonasis-juodasis medis)

• Įdėjimas, ištrynimas, paieška: Vidutiniškai O(log N), blogiausiu atveju – O(log N). N – elementų skaičius.
• Prieiga per raktą naudojant operator[] arba at() metodą: O(log N).
• Iteratoriaus gavimas į pradžią/pabaigą: O(1).
• Visų elementų iteracija: O(N).
• Atmintis: O(N).

std::unordered_map (Hesh lentelė)

• Įdėjimas, ištrynimas, paieška: Vidutiniškai O(1). Blogiausiu atveju – O(N) (stiprios kolizijos). N – elementų skaičius.
• Prieiga per raktą naudojant operator[] arba at() metodą: O(1) vidutiniškai. Blogiausiu atveju – O(N).
• Iteratoriaus gavimas į pradžią/pabaigą: O(1).
• Visų elementų iteracija: O(N) vidutiniškai. Tvarka nėra garantuota.
• Atmintis: O(N). Priklauso nuo apkrovimo koeficiento ir įgyvendinimo.

Palyginimas:

Operacija	std::map (O)	std::unordered_map (O)
Įdėjimas, ištrynimas	log N	1 (vidutiniškai), N (blogiausiu atveju)
Paieška	log N	1 (vidutiniškai), N (blogiausiu atveju)
Prieiga per raktą	log N	1 (vidutiniškai), N (blogiausiu atveju)
Visų elementų iteracija	N	N (vidutiniškai)

std::unordered_map dažniausiai yra greitesnis atskirų operacijų (įdėjimas, paieška, ištrynimas) metu, nes vidutiniškai veikia O(1), tačiau reikalauja gero hash funkcijos ir yra jautrus kolizijoms. std::map garantuoja logaritminę sudėtingumą nepriklausomai nuo duomenų, išlaiko elementus surūšiuotus ir nereikalauja hash funkcijos raktų tipui.