C++ STL Complexities
C++ Standard Template Library Quick Reference
Headers
ne<br>= num elements passed to function
= num elements in container
(back insert)<br>(forward, reversible, rand access)
(back/front insert)<br>(forward, reversible, rand access)
(back/front insert)<br>(forward, reversible)
(forward)
(multiset for duplicate values)
map, multimap
Constructor
default: c;
fill: c(ne, elem, alloc)
range: c(inItA, iItB)
copy: c(const c&)
vector
deque
list
set
map
destructor
~vector
~deque
~list
~set
~map
operator=
operator=
operator=
operator=
operator=
operator=
capacity
size
O(1)
O(1)
O(1)
O(1)
O(1)
max_size [sys limit]
O(1)
O(1)
O(1)
O(1)
O(1)
empty
O(1)
O(1)
O(1)
O(1)
O(1)
capacity
O(1)
reserve(space)
Does not change size
O(n)
resize(n, elem=def)
Changes size
O(n)
O(n)
O(n)
element access
front
O(1)
O(1)
O(1)
back
O(1)
O(1)
O(1)
operator[i]
O(1)
O(1)
O(log n)<br>(map)
at(i)
O(1)
O(1)
Modifiers
(emplace C++11)
assign(iterA, iterB): range
assign(ne, val): fill
O(n)
O(n)
O(ne)
O(ne)
O(ne)
O(ne)
insert(iter, val)
insert(iter, ne, val)
insert(iter, inItA, inItB)
O(n)
O(1)
O(ne)
O(ne)
O(1)
O(ne)
O(ne)
pair insert(val):<br>O(log n)
iter insert(iter, val):<br>O(1)
inIter insert(inItA, inItB):<br>O(ne log n)
O(log n)
O(1)
O(ne log n)
erase(iter)
erase(iterA, iterB)
size_t erase(val)
O(n)
O(n)
O(1)
O(ne)
O(1)
O(ne)
O(1)
O(ne)
O(log n)
O(1)
O(ne)
O(log n)
clear
O(n)
O(n)
O(n)
O(n)
O(n)
swap(container &)
O(1)
O(1)
O(1)
O(1)
O(1)
push_back(val)
O(1)
O(1)
O(1)
pop_back
O(1)
O(1)
O(1)
push_front(val)
O(1)
O(1)
pop_front
O(1)
O(1)
emplace(iter, ne,ele)
O(n)
O(ne)
O(ne)
O(log n)
O(log n)
emplace_back(elem)
O(1)
O(1)
O(1)
emplace_front(elem)
O(1)
O(1)
list operations
remove(val)
O(n)
remove_if(predicate)
O(n)
unique([binaryPred])
O(n - 1)
merge(list &m, [cmp])
O(n + m -1)
reverse
O(n)
sort([cmp])
O(n log n)
splice(iter, list &newLst)<br>splice(iter, list &, inIter)<br>splice(it, list&, inItA, inItB)
O(1)
O(1)
O(ne)
Associate containers operations
count
O(log n)
O(log n)
find
O(log n)
O(log n)
equal_range
O(log n)
O(log n)
lower_bound
O(log n)
O(log n)
upper_bound
O(log n)
O(log n)