###Containers Forward Container: forward iterators - increment only in O(1)
- begin(), end()
- All containers
Reversible Container: bidirectional iterators - increment and decrement in O(1)
- rbegin(), rend()
- vector, deque, list
Random Access Container: bidirectional iterators with O(1) forward and backward
- operator[]
- vector, deque
###Sequence Containers (vector, deque, list) Front Sequence: insert, remove in beginning in O(1)
- front(), push_front(), pop_front()
- deque, list
Back Sequence: insert, remove at end in O(1)
- back(), push_back(), pop_back()
- vector, deque, list
Note about deques: Unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations, thus not allowing direct access by offsetting pointers to elements.
Elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface. Little more complex internally than vectors, but grows more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.
For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists
###Associate Containers (set, map)
Sets and Maps are implemented with self-balancing BST (red/black).
Search, insert, remove takes O(log n). Full iteration is O(n). Copy is O(n log n).
Simple Associate Container: elements are their own keys.
- set, multiset, hash_set, hash_multiset
Pair Associate Container: Associates a key with some other item.
- map, multimap, hash_map, hash_multimap
Unique Associate Container: Keys are unique
- set, map, hash_set, hash_map
Multiple Associate Container: Duplicate keys are possible
- multiset, multimap, hash_multiset, hash_multimap
###Container Adaptors stack (LIFO): Underlying container is deque.
- O(1) operations: push() [front], pop() [front], top()
queue (FIFO): Underlying container is deque.
- O(1) operations: push() [back], pop() [front], front()
Priority_queue: Underlying container is vector and maintained as a max-heap with make_heap().
- O(log n) operations: push() [insert], pop() [front], top() [largest elem]