|
Headers ne = num elements passed to function n = num elements in container |
<vector> (back sequence) (forward, reversible, rand access) |
<deque> (back/front sequence) (forward, reversible, rand access) |
<list> (back/front sequence) (forward, reversible) |
Associative Containers: <set>, <map> |
|
|
Constructor default: c; fill: c(ne, elem, [alloc]) range: c(inItA, iItB) copy: c(const c&) |
vector | deque | list |
set, multiset map, multimap |
|
| capacity | empty(); size(); max_size() – sys or lib limit | O(1) | O(1) | O(1) | O(1) |
| resize(n, elem=def) – changes container size | O(n) | O(n) | O(n) | ||
| capacity | O(1) | ||||
| reserve(space) - does not change size | O(n) | ||||
| Element Access | Iterator: front(), back(). rbegin(), rend() | O(1) | O(1) | O(1) | O(1) |
| operator[i]; at(i) - throws out_of_range | O(1) | O(1) | O(log n) (map) | ||
|
Modifiers
insert returns iterator to first inserted element erase returns iterator to 1 + last removed element |
assign(iterA, iterB): range assign(ne, val): fill |
O(n) O(n) |
O(ne) O(ne) |
O(ne) O(ne) |
|
|
insert(iter, val) – assoc returns pair<it, bool> insert(iter, ne, val) insert(iter, inItA, inItB) |
O(n) O(n) O(n) |
O(1) O(ne) O(ne) |
O(1) O(ne) O(ne) |
O(log n) O(1) O(ne log n) |
|
|
erase(iter) erase(iterA, iterB) |
O(n) O(n) |
O(1) O(ne) |
O(1) O(ne) |
O(1) O(ne) |
|
| size_t erase(val) | O(log n) | ||||
| clear | O(n) | O(n) | O(n) | O(n) | |
| swap(container &) | O(1) | O(1) | O(1) | O(1) | |
| push_back(val); pop_back() | O(1) | O(1) | O(1) | ||
| push_front(val); pop_front() | O(1) | O(1) | |||
| List Operations | remove(val); 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(ne) | ||||
|
Assoc containers operations |
count(); find(); equal_range(); lower_bound(); upper_bound() |
O(log n) | |||
| Container Adaptors |
<priority_queue>
Maintained as max-heap with vector. make_heap: O(3n) |
<queue>
FIFO Implemented with deque |
<stack>
LIFO Implemented with deque |
|
| Capacity | empty(); size() | O(1) | O(1) | O(1) |
| Element Access | front(); back() | O(1) | ||
| top() | O(1) | O(1) | ||
| Modifiers | push() | O(log n) – push_heap | O(1) – push_back | O(1) – push_front |
| pop() | O(log n) – pop_head | O(1) – pop_front | O(1) – pop_font | |