STL Containers


library

Standard Template Library: Containers

A container is a holder object that stores a collection other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.

The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).

Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)...

Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them.

stack, queue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container class independently of the underlying container class used.

Container class templates

Sequence containers:


Container adaptors:


Associative containers:


Member map

This is a comparison chart with the different member functions present on each of the different containers:

Sequence containersAssociative containers
Headers<vector><deque><list><set><bitset>
Memberscomplexvectordequelistsetmultisetmapmultimapbitset
constructor*constructorconstructorconstructorconstructorconstructorconstructorconstructorconstructor
destructorO(n)destructordestructordestructordestructordestructordestructordestructor
operator=O(n)operator= operator= operator= operator= operator= operator= operator= operators
iteratorsbeginO(1)beginbeginbeginbeginbeginbeginbegin
endO(1)endendendendendendend
rbeginO(1)rbeginrbeginrbeginrbeginrbeginrbeginrbegin
rendO(1)rendrendrendrendrendrendrend
capacitysize*sizesizesizesizesizesizesizesize
max_size*max_sizemax_sizemax_sizemax_sizemax_sizemax_sizemax_size
emptyO(1)emptyemptyemptyemptyemptyemptyempty
resizeO(n)resizeresizeresize
element accessfrontO(1)frontfrontfront
backO(1)backbackback
operator[]*operator[] operator[] operator[] operator[]
atO(1)atat
modifiersassignO(n)assignassignassign
insert*insertinsertinsertinsertinsertinsertinsert
erase*eraseeraseeraseeraseeraseeraseerase
swapO(1)swapswapswapswapswapswapswap
clearO(n)clearclearclearclearclearclearclear
push_frontO(1) push_frontpush_front
pop_frontO(1) pop_frontpop_front
push_backO(1)push_backpush_backpush_back
pop_backO(1)pop_backpop_backpop_back
observerskey_compO(1) key_compkey_compkey_compkey_comp
value_compO(1) value_compvalue_compvalue_compvalue_comp
operationsfindO(log n) findfindfindfind
countO(log n) countcountcountcountcount
lower_boundO(log n) lower_boundlower_boundlower_boundlower_bound
upper_boundO(log n) upper_boundupper_boundupper_boundupper_bound
equal_rangeO(log n) equal_rangeequal_rangeequal_rangeequal_range
unique members capacity reserve splice remove remove_if unique merge sort reverse set reset flip to_ulong to_string test any none

Amortized complexity shown. Legend: O(1) constant < O(log n) logarithmic < O(n) linear; *=depends on container

Container adaptors:
Container Adaptors
Headers<stack><queue>
Membersstackqueuepriority_queue
constructor*constructorconstructorconstructor
capacitysizeO(1)sizesizesize
emptyO(1)emptyemptyempty
element accessfrontO(1) front
backO(1) back
topO(1)top top
modifierspushO(1)pushpushpush
popO(1)poppoppop