Ordered Vectors
Table 25 – Time and space requirements for ordered vectors
operation
time cost
space cost
Insert at the end
C (amortized)
t (amortized)
Insert in middle
N/2
t (amortized)
Find (average item)
N/2
0
Change/replace item
C
0
Remove first
N
0
Remove last
C
0
Remove in middle
N/2
0
Container overhead
 
(Mt+ p + 2i) + 0
Comments
Allocation only when the vector grows.
Expands as needed by adding space for many entries at once. Shrinks only via resize()