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

Remove in middle N/2 0
Container overhead (Mt+ p + 2i) + 0
Comments No iterators (use size_t index)
Allocation only when the vector
grows. Expands as needed by adding
space for many entries at once.
Shrinks only via resize()
Sorted Vectors
operation time cost; space cost
Insert logN + N/2 (average) t (amortized)
Find (average item) logN 0
Change/replace item N 0
Remove first N 0
Remove last C 0
Remove in middle N/2 0
Container overhead (Mt + p + 2i) + 0
Comments Insertion happens based on sort
order.
No iterators (use size_t index)
replace requires remove/add
sequence to maintain sorting
Allocation only when the vector
grows. Expands as needed by adding
space for many entries at once.
Shrinks only via resize()
Stacks and Queues
operation time cost; space cost
Insert at end C t + p
Remove (pop) C t + p (recovered)
Container overhead (2p+i) + N(t+p)
Comments: Implemented as singly -linked list.
Templatized version allows choice of container:
time and space costs will reflect that choice.