STL Reference Tables

STM Reference Tables

Containers

All collections have these properties

a series of typedefs
- size_type
- pointer
- const_pointer
- reference
- const_reference
typedefs for creating iterators
- iterator
- const_iterator
- reverse_iterator
- const_reverse_iterator
ctor() to empty state, copy-ctor()
dtor()
bool empty() const
size_type size() const
size_type max_size() const
container-ref operator=(const-container-ref)
replace all contents
void swap(container-ref)
swaps all the contents
bool operator==(const-container-ref)
compare all items for equality
bool operator<(const-container-ref)
begin() and end() methods to access the contents
insert() method
although the prototype is different for sequence and association

Containers and Properties
Container	Default Iterator	Ctors	Accessors	Methods
array	-	-	op[]	-
vector	random-acc	copy	front(), back(), op[], at()	push_back(), pop_back()
bit_vector really vector	random-acc	copy	front(), back(), op[]	push_front(), pop_back(), flip(), assign()
list	bidirectional	copy	-	push_front(), push_back(), pop_front(), pop_back, sort(), splice(), remove(), reverse(), unique(), merge()
deque	random-acc	copy	front(), back(), op[], at()	push_front(), push_back(), pop_front(), pop_back()
Associative
set	bidirectional	copy	find(), lower_bound(), upper_bound(), equal_range()	count()
multiset				count()
map				count(), op[]
multimap				count()
Adaptor
stack	n/a	copy	top()	push(), pop()
queue	n/a	copy	front(), back()	push(), pop()
priority_queue	n/a	copy	top()	push(), pop()
Special
bitset	n/a	copy	front(), back(), op[]	push_front(), pop_back(), test(), any(), none(), op&=, op\|=, op^=, op<<, op>>, set(), reset(), to_ulong(), to_string(), count(), flip()

Iterators

All iterators have these properties

Iterator Properties
Iterator	Ctors	Accessors	Movement Methods	Compare Methods
all	copy		op++(), op++(int)
output	"	op() write only*	"
input	"	op() read only*	"	op= =()
forward	"	op() read write*	", operator=()	"
bidirectional	"	"	", op--(), op--(int)	"
random-access	"	"	", op+=, op+, op-=, op-, op[]	", op<()
C style pointer	"	"	"	"

NOTE: the operator<() is not defined for most iterators.

NOTE: all except output have matching const versions

Special Iterators
istream_iterator iterate-reads a C++ input stream

ostream_iterator iterate-writes to a C++ input stream

back_insert_iterator inserts at back of container

front_insert_iterator inserts at front of container

insert_iterator inserts into container at any position

raw_storage_iterator iterates over uninitialized, allocated memory

reverse_bidirectional_iterator backwards iterator

Special Iterators
istream_iterator	iterate-reads a C++ input stream
ostream_iterator	iterate-writes to a C++ input stream
back_insert_iterator	inserts at back of container
front_insert_iterator	inserts at front of container
insert_iterator	inserts into container at any position
raw_storage_iterator	iterates over uninitialized, allocated memory
reverse_bidirectional_iterator	backwards iterator

Algorithms

In the following table, the argument and return types are coded as follows:

r random access iterator
b bidirectional iterator
f forward iterator
i input iterator
o output iterator

V value
R reference
P pair
B bool

p unary predicate
p2 binary predicate
c compare function
F unary function
F2 binary function
n count
[...] optional args

Algorithms in STL
Name Returns Arguments Function

Finding

adjacent_find i i,i[,p2] find sequence of equal elements

binary_search B f.f.V[,c] find a value in a sorted range

count void i,i,V,R count matching elements

count_if void i,i,p,R count elements which satisfy p

find i i,i,v locate an equal element

find_if i i,i,p locate an element which satisfies p

search f f,f,f,f[,p2] locate a subrange within a range

search f f,f,n,V[,p2] locate a subrange within a range

find_end f f,f,f,f[,p2] find the last subrange which satisfies; like search but from the end

find_first_of f f,f,f,f[,p2] I don't know; the spec is wierd!
lower_bound f f,f,V[,c] returns the first possible insert location into a sorted collection

upper_bound f f,f,V[,c] returns the last possible insert location into a sorted collection

equal_range P f,f,V[,c] returns the range of possible insert locations into a sorted collection

min_element i i,i[,c] find the smallest

max_element i i,i[,c] find the largest

Applying
for_each F f,f,F apply a function to a range

transform o i,i,o,F
i,i,i,o,F2 apply an operation against a range

replace v f,f,V,V replace all matching elements with a new one

replace_if v f,f,p,V replace all matching elements with a new one

replace_copy o i,i,o,V,V replace during copy, all matching elements with a new one

replace_copy_if o i,i,o,p,V replace during copy, all matching elements with a new one

Filling

fill v f,f,V fill with a value

fill_n v f,n,V fill with a single value

generate v f,f,unary_op fill with generated values

generate_n v f,n,unary_op fill with generated values

Enumerating

count v i,i,V,R count the number of matches

count_if v i,i,p2,R count the number of matches, using pred

mismatch P i,i,i[,p2] returns the first subrange than does not match

equal B i,i,i[,p2] true if the ranges match

lexigraphical_compare B i,i,i,[,c] true if the ranges match

Copying

copy o i,i,o copy one range to another

copy_backward b b,b,b reverse copy one range to another

swap_ranges f f,f,f swap one range with another

Ordering

remove f f,f,V move unwanted entries to the end of the range

remove_if f f,f,p move unwanted entries to the end of the range

remove_copy o i,i,o,V copy and remove unwanted entries

remove_copy_if o i,i,o,p copy and remove unwanted entries

unique f f,f[,p2] collapse the range so that multiple copies of equal elements are removed

unique_copy o i.i,o[,p2] copy the range skipping multiple copies of equal elements

reverse v b,b reverse the order of a range

reverse_copy o b,b,o reverse the order of a range

rotate v f,f,f rotate a range, given first, middle and last

rotate_copy o f,f,f,o rotate and copy, given first, middle and last

random_shuffle v r,r[,rand_gen] shuffle the order of a range

Sorting

partition b b,b,p swaps to make all the pred-successes precede the pred-failures

stable_partition b b,b,p swaps to make all the pred-successes precede the pred-failures; preserves relative order

sort v r,r[,c] sorts the elements in the range

stable_sort v r,r[,c] sorts the range; preserve relative order on the "equal" ones

partial_sort v r,r,r[,c] sorts the range into the subrange

partial_sort_copy r i,i,r,r[,c] sorts the range into the subrange at a new location

nth_element v r,r,r[,c] sorts the range so that one specific one is in the right place

next_permutation B b,b[,c] transforms range to next permutation

prev_permutation tranforms range to previous permutation

Merging

merge o i,i,i,i,o[,c] merges two input ranges

inplace_merge v b,b,b[,c] merges two input ranges

Set Support

includes b i,i,i,i[,c] tests for the elementf of one range present in another

set_union
set_intersection
set_difference
set_symmetric_difference o i,i,i,i,o[,c] builds the sorted union
intersection
difference
symmetric_difference

Heap Support

push_heap v r,r[,c] adds the last element of a range to a heap

pop_heap changes a heap into a smaller heap plus a last element

make_heap changes a range into a heap

sort_heap sorts a heap

Name	Returns	Arguments	Function
Finding
adjacent_find	i	i,i[,p2]	find sequence of equal elements
binary_search	B	f.f.V[,c]	find a value in a sorted range
count	void	i,i,V,R	count matching elements
count_if	void	i,i,p,R	count elements which satisfy p
find	i	i,i,v	locate an equal element
find_if	i	i,i,p	locate an element which satisfies p
search	f	f,f,f,f[,p2]	locate a subrange within a range
search	f	f,f,n,V[,p2]	locate a subrange within a range
find_end	f	f,f,f,f[,p2]	find the last subrange which satisfies; like search but from the end
find_first_of	f	f,f,f,f[,p2]	I don't know; the spec is wierd!
lower_bound	f	f,f,V[,c]	returns the first possible insert location into a sorted collection
upper_bound	f	f,f,V[,c]	returns the last possible insert location into a sorted collection
equal_range	P	f,f,V[,c]	returns the range of possible insert locations into a sorted collection
min_element	i	i,i[,c]	find the smallest
max_element	i	i,i[,c]	find the largest
Applying
for_each	F	f,f,F	apply a function to a range
transform	o	i,i,o,F i,i,i,o,F2	apply an operation against a range
replace	v	f,f,V,V	replace all matching elements with a new one
replace_if	v	f,f,p,V	replace all matching elements with a new one
replace_copy	o	i,i,o,V,V	replace during copy, all matching elements with a new one
replace_copy_if	o	i,i,o,p,V	replace during copy, all matching elements with a new one
Filling
fill	v	f,f,V	fill with a value
fill_n	v	f,n,V	fill with a single value
generate	v	f,f,unary_op	fill with generated values
generate_n	v	f,n,unary_op	fill with generated values
Enumerating
count	v	i,i,V,R	count the number of matches
count_if	v	i,i,p2,R	count the number of matches, using pred
mismatch	P	i,i,i[,p2]	returns the first subrange than does not match
equal	B	i,i,i[,p2]	true if the ranges match
lexigraphical_compare	B	i,i,i,[,c]	true if the ranges match
Copying
copy	o	i,i,o	copy one range to another
copy_backward	b	b,b,b	reverse copy one range to another
swap_ranges	f	f,f,f	swap one range with another
Ordering
remove	f	f,f,V	move unwanted entries to the end of the range
remove_if	f	f,f,p	move unwanted entries to the end of the range
remove_copy	o	i,i,o,V	copy and remove unwanted entries
remove_copy_if	o	i,i,o,p	copy and remove unwanted entries
unique	f	f,f[,p2]	collapse the range so that multiple copies of equal elements are removed
unique_copy	o	i.i,o[,p2]	copy the range skipping multiple copies of equal elements
reverse	v	b,b	reverse the order of a range
reverse_copy	o	b,b,o	reverse the order of a range
rotate	v	f,f,f	rotate a range, given first, middle and last
rotate_copy	o	f,f,f,o	rotate and copy, given first, middle and last
random_shuffle	v	r,r[,rand_gen]	shuffle the order of a range
Sorting
partition	b	b,b,p	swaps to make all the pred-successes precede the pred-failures
stable_partition	b	b,b,p	swaps to make all the pred-successes precede the pred-failures; preserves relative order
sort	v	r,r[,c]	sorts the elements in the range
stable_sort	v	r,r[,c]	sorts the range; preserve relative order on the "equal" ones
partial_sort	v	r,r,r[,c]	sorts the range into the subrange
partial_sort_copy	r	i,i,r,r[,c]	sorts the range into the subrange at a new location
nth_element	v	r,r,r[,c]	sorts the range so that one specific one is in the right place
next_permutation	B	b,b[,c]	transforms range to next permutation
prev_permutation	B	b,b[,c]	tranforms range to previous permutation
Merging
merge	o	i,i,i,i,o[,c]	merges two input ranges
inplace_merge	v	b,b,b[,c]	merges two input ranges
Set Support
includes	b	i,i,i,i[,c]	tests for the elementf of one range present in another
set_union set_intersection set_difference set_symmetric_difference	o	i,i,i,i,o[,c]	builds the sorted union intersection difference symmetric_difference
Heap Support
push_heap	v	r,r[,c]	adds the last element of a range to a heap
pop_heap			changes a heap into a smaller heap plus a last element
make_heap			changes a range into a heap
sort_heap			sorts a heap