(multi)map and (multi)set family

Table 30 – Time and space requirements for (multi)map and (multi)set family
operation	time cost	space cost
Insert	logN+C	2p+t
Find (average item)	logN	0
Change/replace item	2(logN+C) or C	0
Remove first	logN (worst case)	2p+t (recovered)
Remove last	logN (worst case)	2p+t (recovered)
Remove in middle	logN (worst case)	2p+t (recovered)
Container overhead	re-balance may occur at each insert or remove	(3p+i) + N(2p+t)
Comments	Insertion happens based on sort order. Allocation with each insert Replace for sets requires remove/insert. For maps the value is copied in place. Implemented as balanced (red-black) binary tree.