Kāda ir sarežģītība darbā ar map un unordered_map konteineriem C++?

std::map (Sarkano-melnā koks)

• Ievietošana, dzēšana, meklēšana: Vidēji O(log N), sliktākajā gadījumā – O(log N). N ir elementu skaits.
• Piekļuve pēc atslēgas ar operator[] vai at() metodi: O(log N).
• Iteratora iegūšana uz sākumu/beigu: O(1).
• Visu elementu iterācija: O(N).
• Atmiņa: O(N).

std::unordered_map (Hesh tabula)

• Ievietošana, dzēšana, meklēšana: Vidēji O(1). Sliktākajā gadījumā – O(N) (stipras kolīcijas). N – elementu skaits.
• Piekļuve pēc atslēgas ar operator[] vai at() metodi: O(1) vidēji. Sliktākajā gadījumā – O(N).
• Iteratora iegūšana uz sākumu/beigu: O(1).
• Visu elementu iterācija: Vidēji O(N). Kārtība nav garantēta.
• Atmiņa: O(N). Atkarīga no slodzes koeficienta un hesh tabulas realizācijas.

Salīdzinājums:

Operācija	std::map (O)	std::unordered_map (O)
Ievietošana, dzēšana	log N	1 (vidēji), N (sliktākajā)
Meklēšana	log N	1 (vidēji), N (sliktākajā)
Piekļuve ar atslēgu	log N	1 (vidēji), N (sliktākajā)
Visu elementu iterācija	N	N (vidēji)

std::unordered_map parasti ir ātrāks individuālām operācijām (ievietošana, meklēšana, dzēšana) ar O(1) vidēji, bet prasa labu hash funkciju un ir jutīgs pret kolīzijām. std::map garantē logaritmisku sarežģītību neatkarīgi no datiem, saglabā elementus sakārtotā secībā un neprasa hash funkciju atslēgas tipam.