Wat is de complexiteit van werken met de containers map en unordered_map in C++?

std::map (Rode-zwart boom)

• Invoegen, verwijderen, zoeken: O(log N) gemiddeld en in het slechtste geval. N is het aantal elementen.
• Toegang via sleutel met operator[] of at(): O(log N).
• Iterators naar begin/einde: O(1).
• Iteratie over alle elementen: O(N).
• Geheugen: O(N).

std::unordered_map (Hash-tabel)

• Invoegen, verwijderen, zoeken: O(1) gemiddeld. O(N) in het slechtste geval (bij sterke hash-collisies). N is het aantal elementen.
• Toegang via sleutel met operator[] of at(): O(1) gemiddeld. O(N) in het slechtste geval.
• Iterators naar begin/einde: O(1).
• Iteratie over alle elementen: O(N) gemiddeld. De volgorde van iteratie is niet gegarandeerd.
• Geheugen: O(N). Afhankelijk van de laadfactor en de implementatie van de hash-tabel.

Vergelijking:

Operatie	std::map (O)	std::unordered_map (O)
Invoegen, verwijderen	log N	1 (gemiddeld), N (slechtste)
Zoeken	log N	1 (gemiddeld), N (slechtste)
Toegang via sleutel	log N	1 (gemiddeld), N (slechtste)
Iteratie over alle elementen	N	N (gemiddeld)

std::unordered_map is over het algemeen sneller voor enkele operaties (invoegen, zoeken, verwijderen) dankzij O(1) gemiddeld, maar vereist een goede hash-functie en is gevoelig voor collisions. std::map garandeert logaritmische complexiteit onafhankelijk van de gegevens, houdt de elementen gesorteerd en vereist geen hash-functie voor het sleuteltype.