C++ Standard Template Library (STL) containers

The C++ STL containers are categorized into sequence containers (vector, deque, list) and associative containers (set, map), each with specific iterator capabilities and time complexities for operations. Sequence containers support front and back insertion/removal in O(1) time, while associative containers use self-balancing binary search trees for O(log n) search, insert, and remove operations. Container adaptors like stack, queue, and priority_queue provide restricted interfaces built on underlying containers such as deque or vector.

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