| Headers | <vector> | <deque> | <list> | <set> | <map> | |
|---|---|---|---|---|---|---|
|
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) | ||||