Annexe B Carte de référence STL

B.1 Les containers

Tous les containers sont dotés des caractéristiques suivantes :

Certains types prédéfinis (typedefs) :
- size_type
- pointer
- const_pointer
- reference
- const_reference
Des types prédéfinis pour la création d'itérateurs :
- iterator
- const_iterator
- reverse_iterator
- const_reverse_iterator
constructor() : pour la création de containers vides
copy-constructor()
destructor()
bool empty() const
size_type size() const : nombre d'éléments du container
size_type max_size() const : capacité (mémoire occupée) maximum du container
container-ref operator=(const-container-ref) : remplacement de tout le contenu
void swap(container-ref) : inverse tout le contenu
bool operator==(const-container-ref) : teste l'égalité sur tous les éléments
bool operator<(const-container-ref)
begin() et end() : méthodes pour accéder au contenu
insert()

Propriétés des containers

Container	Iterateur par déf.	Constructeurs	Accesseurs	Méthodes
array	-	-	op[]	-
vector	random-acc	copy	front(), back(), op[], at()	push_back(), pop_back()
bit_vector	random-acc	copy	front(), back(), op[]	push_front(), pop_back(), flip(), assign()
list	bidirectional	copy	front(), back()	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	bidirectional	copy	find(), lower_bound(), upper_bound(), equal_range()	count()
map	bidirectional	copy	find(), lower_bound(), upper_bound(), equal_range()	count(), op[]
multimap	bidirectional	copy	find(), lower_bound(), upper_bound(), equal_range()	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()

B.2 Les itérateurs

Propriété des itérateurs

Iterateur	Constructeurs	Accesseurs	Déplacement	Comparaison
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	"	"	"	"

Itérateurs spéciaux

istream_iterator	lit un flot d'entrée C++
ostream_iterator	écrit dans un flot de sortie C++
back_insert_iterator	insère à la fin d'un container
front_insert_iterator	insère au début d'un container
insert_iterator	insère dans un container à n'importe quelle position
raw_storage_iterator	itérateur sur mémoire allouée non initialisée
reverse_bidirectional_iterator	itérateur dans le sens inverse

B.3 Les algorithmes

Dans le tableau suivant, les arguments des fonctions et des valeurs de retour sont codés de la manière suivante :

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

Algorithmes en STL

Nom	Retourne	Arguments	Description
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
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 or 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
lexicographical_compare	B	i,i,i,[,c]	true if the ranges match

Nom	Retourne	Arguments	Description
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

Nom	Retourne	Arguments	Description
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	o	i,i,i,i,o[,c]	builds the sorted union
set_intersection	o	i,i,i,i,o[,c]	intersection
set_difference	o	i,i,i,i,o[,c]	difference
set_symmetric_difference	o	i,i,i,i,o[,c]	symmetric_difference
Heap Support
push_heap	v	r,r[,c]	adds the last element of a range to a heap
pop_heap	v	r,r[,c]	changes a heap into a smaller heap plus a last element
make_heap	v	r,r[,c]	changes a range into a heap
sort_heap	v	r,r[,c]	sorts a heap