Instruction Manual

differ radically among various implementations. However, it is generally true that a heap
allocation (or deallocation) that translates to a system call is more expensive than most of the
other constant costs. "Amortized" cost is averaged over the life of the collection. Any individual
action may have a higher or lower cost than the amortized value.
Key to the comparison tables
N M t i p C
count of items count of space for
items
sizeof (item) sizeof (int) sizeof (void*) a constant
RWGVector, RWGBitVec, RWBitVec<size>, RWTPtrVector, and
RWTValVector
operation time cost space cost
Insert at an end C 0
Insert in middle C 0
Find (average item) N/2 0
Change/replace item C 0
Remove first C 0
Remove last C 0
Remove in middle C 0
Container overhead Mt + 0
Comments Simple wrapper around an array of T (except
bitvec: array of byte)
Resize only if told to.
Singly Linked Lists
operation time cost; space cost
Insert at an end C t + p
Insert in middle C (assumes that you have an
iterator in position)
t + p
Find (average item) N/2 0
Change/replace item C 0
Remove first C t + p (recovered)