Milline on töö keerukus C++-is map ja unordered_map konteineritega?

std::map (Punase-musta puu)

• Lisamine, kustutamine, otsing: Keskmiselt ja halvimal juhul O(log N). N on elementide arv.
• Juurdepääs võtme kaudu operator[] või meetodi at(): O(log N).
• Iteraatori saamine algusest/lõpust: O(1).
• Kõigi elementide iteratsioon: O(N).
• Mälu: O(N).

std::unordered_map (Hüper-tabel)

• Lisamine, kustutamine, otsing: Keskmiselt O(1). Halvimal juhul O(N) (kui hash-kolisiioone on palju). N on elementide arv.
• Juurdepääs võtme kaudu operator[] või meetodi at(): O(1) keskmiselt. Halvimal juhul O(N).
• Iteraatori saamine algusest/lõpust: O(1).
• Kõigi elementide iteratsioon: Keskmiselt O(N). Iteratsiooni järjekord ei ole garanteeritud.
• Mälu: O(N). Sõltub laadimiskordajast ja hüper-tabeli teostusest.

Võrdlus:

Operatsioon	std::map (O)	std::unordered_map (O)
Lisamine, kustutamine	log N	1 (keskmiselt), N (halvimal juhul)
Otsing	log N	1 (keskmiselt), N (halvimal juhul)
Juurdepääs võtme kaudu	log N	1 (keskmiselt), N (halvimal juhul)
Kõigi elementide iteratsioon	N	N (keskmiselt)

std::unordered_map on tavaliselt kiirem üksikute operatsioonide (lisamine, otsing, kustutamine) puhul tänu O(1) keskmiselt, kuid nõuab head hash-funktsiooni ning on tundlik kolisioonide suhtes. std::map tagab logaritmilise keerukuse sõltumata andmetest, säilitab elemendid sorteeritud järjekorras ning ei nõua hash-funktsiooni võtmetüübile.