C++ STL Containers at a Glance
Updated for C++20
Type Container Description Iterator Implementation Performance Similar Container Comments
pair<K,V> pair of ANY objects NOT a Container
-
tuple<T…> Generalization of pair with more object types pair<K,V>
array<T,N> fixed-size array contiguous vector<T> (fixed size)
Not a real array.
Low memory foot-
bitset<N> fixed-size sequence of N bits - Elements are stored array<T,N>
print
in special way.
Sequence
vector<T> variable-size array contiguous The Most Commonly-Used
deque<T> double-ended queue random access vector<T> (double-ended) Use if size changes frequently
Slower than
list<T> doubly-linked list bidirectional Can be scattered in vector<T>
the memory
forward_list<T> single-linked list forward Slower than list<T>
Lookup cost is
map<K,V> associative array of “pair<K,V>” (key & value) Binary Tree O(log(n)), which is
bidirectional Type needs to very quick
implement “<”
multimap<K,V> map in which a key may occur more than once map<K,V> NOT supporting [ ]
unordered_map<K,V> map (stored not ordered) Hash Tbale map<K,V>
Type needs to
Associative
forward
unordered_multimap<K,V> multimap (stored not ordered) implement “==” & multimap<K,V>
With a good hashing
hash function
function
Equality is decided by expression:
set<T> set (a map with just a key and no value) Binary Tree unordered versions map<K,V>
(!(X < Y) && !(Y < X))
bidirectional Type needs to show better
multiset<T> set in which a value may occur more than once implement “<” performance set<T>
unordered_set<T> set (stored not ordered) Hash Tbale set<T>
Type needs to
forward
unordered_multiset<T> multiset (stored not ordered) implement “==” & multiset<T>
hash function
stack
Adaptors
queue Can be any of above
No Iterators containers
when front() is called the smallest member
priority_queue queue
(determined by "<") will be popped out
Single A3 – Size (Landscape) Sheet Compiled & Prepared by: Pouya Ebadollahyvahed (Linked-in) July 17th, 2024
