Sorted Vectors

SourcePro Core : Essential Tools Module User's Guide : Appendix A, Choosing a Collection : Time and Space Considerations : Sorted Vectors

Sorted Vectors

Table 26 – Time and space requirements for 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. For RWSortedVector, use RWOrderedIterator to iterate over the collection. 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()