SourcePro Core : Essential Tools Module User's Guide : Appendix A, Choosing a Collection : Time and Space Considerations : Deques
Deques
Table 28 – Time and space requirements for deques
operation
time cost
space cost
Insert at end
C
t (amortized)
Find (average item)
N/2
0
Change/replace item
C
0
Remove first
C
t (amortized, recovered)
Remove last
C
t (amortized, recovered)
Remove in middle
N/2
t (amortized, recovered)
Container overhead
 
(Mt + p + i) + 0
Comments
Implemented as circular queue in an array.
Allocation only when collection grows
Expands and shrinks as needed, caching extra expansion room with each increase in size
Additional product documentation
About SourcePro
SourcePro Resources
Technical Support
Visit us at: https://www.perforce.com/support/request-support

Copyright © 2023 Perforce Software, Inc. All rights reserved.