HP Integrity NonStop J-Series - Manual (Page 306)

(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.
RWBTree, RWBTreeDictionary [32]
operation time cost; space cost
Insert logN+C 2p + t + small (fully
amortized)
Find (average item) logN 0
Change/replace item 2logN+2 or C 0
Remove first 2logN(log2(ORDER))+C
(worst case) 2p+t (recovered)
Remove last 2logN(log2(ORDER))+C
(worst case) 2p+t (recovered)
Remove in middle 2logN(log2(ORDER))+C (worst case) 2p+t (recovered)