ne
= num elements passed to function
n
= num elements in container
|
(back insert)
(forward, reversible, rand access)
|
(back/front insert)
(forward, reversible, rand access)
|
(back/front insert)
(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)
(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<it, bool> insert(val):
O(log n)
iter insert(iter, val):
O(1)
inIter insert(inItA, inItB):
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)
splice(iter, list &, inIter)
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)
|