C++ Containers Cheat Sheet

Key

X	= container class	a, b	= objects of class X
T	= class which is stored in X	t	= object of class T
n	= number	i, j	= iterators of any type
p, q, hint	= iterators of type X	key	= object of key class for X
comp	= comparator object	pred	= predicate object
bin_pred	= binary predicate object	c	= container object being adapted

Containers

template<class T, class A=allocator<T> > class vector
template<class T, class A=allocator<T> > class list
template<class T, class A=allocator<T> > class deque
template<class T, class Compare=less<T>, class A=allocator<T> > class set
template<class T, class Compare=less<T>, class A=allocator<T> > class multiset
template<class Key, class Mapped, class Compare=less<Key>, class A=allocator<Mapped> > class map
template<class Key, class Mapped, class Compare=less<Key>, class A=allocator<Mapped> > class multimap
template<class T, class Traits=char_traits<T>, class A=allocator<T> > class basic_string
template<class T, class Hash=hash<T>, class Eq=equal_to<T>, class A=allocator<T> > class hash_set
template<class T, class Hash=hash<T>, class Eq=equal_to<T>, class A=allocator<T> > class hash_multiset
template<class Key, class Mapped, class Hash=hash<Key>, class Eq=equal_to<Key>, class A=allocator<Mapped> > class hash_map
template<class Key, class Mapped, class Hash=hash<Key>, class Eq=equal_to<Key>, class A=allocator<Mapped> > class hash_multimap
template<class T, class Container=deque<T> > class stack
template<class T, class Container=deque<T> > class queue
template<class T, class Container=vector<T>, class Compare=less<class Container::value_type> > class priority_queue


Expressions grouped by container requirements,      * = non-standard container

Container

Expression	Return type	vector	list	deque	basic string	set	multi  set	map	multi  map	hash  set*	hash  multi set*	hash  map*	hash  multi map*	stack	queue	priority queue
X::value_type	T
X::reference	lvaue of T
X::const_reference	const lvalue of T
X::iterator	iterator to T
X::const_iterator	iterator to const T
X::difference_type	signed integral type
X::size_type	unsigned integral type
X a
X a(b)
a.~X()
a = b	X&
swap(a, b)	void
a == b	convertible to bool
a < b	convertible to bool
a.begin()	iterator or const_iterator
a.end()	iterator or const_iterator
a.size()	size_type
a.max_size()	size_type
a.empty()	convertible to bool
a.swap(b)	void

Reversable Container

Expression	Return type	vector	list	deque	basic string	set	multi  set	map	multi  map	hash  set*	hash  multi set*	hash  map*	hash  multi map*	stack	queue	priority queue
X::reverse_iterator	iterator to T
X::const_reverse_iterator	iterator to const T
a.rbegin()	reverse_iterator or const_reverse_iterator
a.rend()	reverse_iterator or const_reverse_iterator

Sequence

Expression	Return type	vector	list	deque	basic string	set	multi  set	map	multi  map	hash  set*	hash  multi set*	hash  map*	hash  multi map*	stack	queue	priority queue
X a(n, t)
X a(i, j)
a.insert(p, t)	iterator
a.insert(p, n, t)	void
a.insert(p, i, j)	void
a.erase(q)	iterator
a.erase(p, q)	iterator
a.clear()	void
a.back()	reference or const_reference
a.push_back(t)	void
a.pop_back()	void
a.front()	reference or const_reference
a.push_front(t)	void
a.pop_front()	void
a[n]	reference or const_reference
a.at(n)	reference or const_reference

Associative Container

Expression	Return type	vector	list	deque	basic string	set	multi  set	map	multi  map	hash  set*	hash  multi set*	hash  map*	hash  multi map*	stack	queue	priority queue
X::key_type	Key
X::key_compare	Compare
X::value_compare
X a(comp)
X a
X a(i, j, comp)
X a(i, j)
a.key_comp()	key_compare
a.value_comp()	value_compare
a.insert(t)	pair<iterator, bool>
	iterator
a.insert(hint, t)	iterator
a.insert(i, j)	void
a.erase(key)	size_type
a.erase(q)	void
a.erase(p, q)	void
a.clear()	void
a.find(key)	iterator or const_iterator
a.count(key)	size_type
a.lower_bound(k)	iterator or const_iterator
a.upper_bound(k)	iterator or const_iterator
a.equal_range(k)	pair<iterator,      iterator> or pair<const_iterator,      const_iterator>

Container Specific

Expression	Return type	vector	list	deque	basic string	set	multi  set	map	multi  map	hash  set*	hash  multi set*	hash  map*	hash  multi map*	stack	queue	priority queue
a.get_allocator()	allocator_type
a.assign(p, q)	void
a.resize(n)	void
a.resize(n, t)	void
a.assign(n, t)	void
a.capacity()	size_type
a.reserve(n)	void
a.splice(p, b)	void
a.splice(p, b, i)	void
a.splice(p, b, i, j)	void
a.remove(t)	void
a.remove_if(pred)	void
a.unique()	void
a.unique(bin_pred)	void
a.merge(b)	void
a.merge(b, comp)	void
a.reverse()	void
a.sort(comp)	void
X::mapped_type	Mapped (T.second)
a[key]	mapped_type
X::container_type	Container
X a(c)
X a(comp, c)
X a(i, j, comp, c)
a.push(t)	void
a.pop()	void
a.top()	T& or const T&
a.front()	T& or const T&
a.back()	T& or const T&

Choosing a Container