Programming‎ > ‎C++‎ > ‎

STL Containers

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).
 

Member map

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

Sequence containers Associative containers
Headers <vector> <deque> <list> <set> <map> <bitset>
Members complex vector deque list set multiset map multimap bitset
constructor * constructor constructor constructor constructor constructor constructor constructor constructor
destructor O(n) destructor destructor destructor destructor destructor destructor destructor
operator= O(n) operator= operator= operator= operator= operator= operator= operator= operators
iterators begin O(1) begin begin begin begin begin begin begin
end O(1) end end end end end end end
rbegin O(1) rbegin rbegin rbegin rbegin rbegin rbegin rbegin
rend O(1) rend rend rend rend rend rend rend
capacity size * size size size size size size size size
max_size * max_size max_size max_size max_size max_size max_size max_size
empty O(1) empty empty empty empty empty empty empty
resize O(n) resize resize resize
element access front O(1) front front front
back O(1) back back back
operator[] * operator[] operator[] operator[] operator[]
at O(1) at at
modifiers assign O(n) assign assign assign
insert * insert insert insert insert insert insert insert
erase * erase erase erase erase erase erase erase
swap O(1) swap swap swap swap swap swap swap
clear O(n) clear clear clear clear clear clear clear
push_front O(1) push_front push_front
pop_front O(1) pop_front pop_front
push_back O(1) push_back push_back push_back
pop_back O(1) pop_back pop_back pop_back
observers key_comp O(1) key_comp key_comp key_comp key_comp
value_comp O(1) value_comp value_comp value_comp value_comp
operations find O(log n) find find find find
count O(log n) count count count count count
lower_bound O(log n) lower_bound lower_bound lower_bound lower_bound
upper_bound O(log n) upper_bound upper_bound upper_bound upper_bound
equal_range O(log n) equal_range equal_range equal_range equal_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>
Members stack queue priority_queue
constructor * constructor constructor constructor
capacity size O(1) size size size
empty O(1) empty empty empty
element access front O(1) front
back O(1) back
top O(1) top top
modifiers push O(1) push push push
pop O(1) pop pop pop

 

Subpages (2): Bitset Deque
Comments