containers.txt

                
   CONTAINERS   
                

                    /=+===============================+=\ 
                   /  :                               :  \  
                   )==:            RESUME             :==(   
                   \  :_______________________________:  /    
                    \=+===============================+=/

tous                : ::size_type,        ::difference_type,  ::allocator_type,   ::pointer,          ::reference,        
                      ::const_pointer,    ::const_reference
tous                : begin(),            end(),              rbegin(),           rend(),             size(), 
                      max_size(),         empty(),          erase(ITVR[, ITVR2]), swap(CONTAINER),   clear()
                      get_allocator()
::[const_][reverse_]: random (vector, deque),                 bidirectionnal (list, set, multiset, map, multimap), 
iterator              forward (vector<bool>, deque<bool>, list<bool>) 
vector, deque, 
list, set, multiset : ::value_type
_______________________________________________________________________________________________________________________________

vector, deque, list : <WVAR[, ALLOCATOR]>, const([ALLOCATOR]), const(SIZE_TYPE_VAL[, WVAR_VAL][, ALLOCATOR]), 
                      const(ITVR1, ITVR2), resize(SIZE_TYPE_VAL[, WVAR_VAL]),     front(),            back(), 
                      assign(SIZE_TYPE_VAL, WVAR_VAL),      assign(ITVR1, ITVR2), push_back(WVR_VAL), pop_back(), 
                      insert(ITVR[, SIZE_TYPE_VAL], WVAR_VAL), insert(ITVR1, ITVR2, ITVR3)
vector, deque       : [SIZE_TYPE_VAL], at(SIZE_TYPE_VAL)
deque, list         : push_front(WVAR_VAL), pop_front()
vector              : capacity(), reserve(SIZE_TYPE_VAL)
list                : splice(ITVR, LIST[, ITVR2, ITVR3]),     sort([FONC_ADR]),   splice(ITVR, LIST, ITVR2), 
                      remove(WVAR_VAL),   reverse(),          remove_if([FONC_ADR]), unique([FONC_ADR]), merge(LIST[, FONCADR])
_______________________________________________________________________________________________________________________________

set, map, multiset, : const([PREDIC][, ALLOCATOR]), lower_bound(WVAR_VAL), 
multimap              const(ITVR1, ITVR2, [PREDIC][, ALLOCATOR]), ::key_type,     ::key_compare,       key_comp(), 
                      ::value_compare,    upper_bound(WVAR_VAL), count(WVAR_VAL), value_comp(),       equal_range(WVAR_VAL), 
                      find(WVAR_VAL),     erase(WVAR_VAL)
set, multiset       : <WVAR[, PREDIC_TYPE][, ALLOCATOR]>,     insert(WVAR_VAL),   insert(ITVR1, WVAR_VAL), insert(ITVR1, ITVR2)
map, multimap       : <WVAR, WVAR2[, PREDIC_TYPE][, ALLOCATOR]>, ::mapped_type,   ::value_type
map                 : [WVAR_VAL], insert(PAIR)
multiset, multimap  : insert([ITVR, ]WVAR_VAL), insert(ITVR1, ITVR2)
_______________________________________________________________________________________________________________________________

stack, queue, 
priority_queue      : size(),             empty(),            push(WVAR_VAL),     pop()
queue               : front(),            back()
stack, 
priority_queue      : top()
stack, queue        : <WVAR[, CONT_TYPE]>
priority_queue      : <WVAR[, CONT_TYPE[, PREDIC_TYPE]]>, const([PREDIC]),        const(PREDIC, CONTAINER), 
                      const(ITVR1, ITVR2[, PREDIC[, CONTAINER]])
_______________________________________________________________________________________________________________________________

bad_alloc           : resize, reserve, push_back, push_front, insert, pop

                    /=+===============================+=\ 
                   /  :                               :  \  
                   )==:          GENERALITES          :==(   
                   \  :_______________________________:  /    
                    \=+===============================+=/ 

TYPES DE CONTAINERS ==> #Il y a :
                        #  - les sequence containers : vector, deque, list
                        #  - les associative containers : set, multiset, map, 
                        #    multimap
                        #  - les containor adaptors : stack, queue, 
                        #    priority_queue
                        #  - bitset
                        #  - les strings sont des sorte de containers

INDEXS ==>              #Les indexs commencent à 0.

CONTAINERS ==>          #Contrairement à leur implémentation possible en C,
                        #parmi les nombreux avantages du fait qu'il s'agit de
                        #classes C++, il y a le fait que l'allocation de leur 
                        #mémoire est automatiquement pris en charge.

CODIFICATION ==>        #Voici le sens dans ma documentation de ces mots. Il
                        #s'agit d'instantiations de :
TOU_CONT                #vector, deque, list, set, multiset et string (mais pas
                        #map ou multimap)
A_S_CONT                #vector, deque, list, set, multiset, map ou multimap
SEQ_CONT                #vector, deque ou list
VEC-DEQ                 #vector ou deque
DEQ-LIST                #deque ou list
ASS_CONT                #set, multiset, map ou multimap
SET_CONT                #set ou multiset
SET-MAP                 #set ou map
MSET-MMAP               #multiset ou multimap
ADA_CONT                #stack, queue ou priority_queue
                        #Ou des mots :
a_s_cont                #"vector", "deque", "list", "set", "multiset", "map" ou 
                        #"multimap"
s_s_cont                #"vector", "deque", "list", "set" ou "multiset"
seq_cont                #"vector", "deque" ou "list"
vec-deq                 #"vector" ou "deque"
deq-list                #"deque" ou "list"
set_cont                #"set" ou "multiset"
map_cont                #"map" ou "multimap"

SEQUENCE CONTAINERS ==> #Suite linéaire d'éléments : intérêt est dans l'accès
                        #via leur position dans le container (que ce soit 
                        #random access ou sequential).

VECTOR ==>              #Semblable à une dynamique array.
                        #  - Les éléments sont contigus dans la mémoire.
                        #  - Il est possible d'utiliser une arithmétique de 
                        #    pointeurs (préférer les iterators).
                        #  - Il est possible de manipuler la mémoire allouée.
                        #  - Seule l'insertion vers la fin est possible.

DEQUE ==>               #Semblable à vector, mais :
                        #  - tous les éléments ne sont pas toujours contigus 
                        #    dans la mémoire, mais organisés en plusieurs 
                        #    morceaux : réallocation moins coûteuse que vectors
                        #  - possibilité d'insérer des éléments au début

LIST ==>                #Double-linked list.
                        #  - chaque élément est isolé en mémoire, lié à
                        #    l'élément suivant et précédant
                        #  - l'ensemble reste linéaire
                        #  - bonne insertion, et déplacement
                        #  - pas de random access

ASSOCIATIVE             #Ensemble de clefs, associées ou non à une valeur : 
CONTAINERS ==>          #intérêt est dans l'accès via la valeur de cette clef.
                        #Les clefs sont automatiquement triées dans le container
                        #lors de leur insertion, en fonction d'une fonction de
                        #tri que l'on précise.
                        #L'écriture ne fait que via insert(), =, le constructor
                        #(et [] pour les maps).

SET ==>                 #Chaque élément est une clef. Implémenté généralement 
                        #sous forme de binary tree. 
                        #  - deux éléments ne peuvent pas avoir la même clef. 
                        #On peut accéder aux éléments :
                        #  - avec le clef
                        #  - avec l'itérateur (moins d'intérêt)

MULTISET ==>            #Comme les sets, sauf que plusieurs éléments peuvent 
                        #avoir la même clef : les clefs doublons ne sont pas 
                        #supprimées avec insert() et les constructors.

MAP ==>                 #Comme les sets, mais chaque clef est associée à une 
                        #valeur.
                        #  - Un élément est donc une PAIR <const WVAR, WVAR2> 
                        #  - les iterators peuvent désigner les deux via 
                        #    ITERATOR_VAR->first et ITERATOR_VAR->second. Il ne
                        #    suffit donc pas de les déférencer avec *ITRTR_VAR
                        #  - L'operator[] est disponible pour accéder aux 
                        #    valeurs des clefs grâce aux clefs.
                        #  - Comme les sets, les clefs ayant la même valeur 
                        #    sont supprimées automatiquement.

MULTIMAP ==>            #Comme les maps, sauf que plusieurs éléments peuvent 
                        #avoir la même clef : les clefs doublons ne sont pas 
                        #supprimées avec insert() et les constructors.
                        #L'operator[] n'est pas disponible.

CONTAINER ADAPTORS ==>  #Il s'agit de containers basés sur d'autres adaptors et
                        #en limitant les fonctions pour leut donner une fonction
                        #précise. Ils ne peuvent pas avoir d'iterators.

STACK ==>               #Il s'agit d'un LIFO
QUEUE ==>               #Il s'agit d'un FIFO
PRIORITY_QUEUE ==>      #Il s'agit d'un heap, c'est-à-dire un binary tree où 
                        #chaque node est plus grand que chaque enfant.
                        #Il est facile dans un heap d'accéder à la valeur min et
                        #max, permettant donc de supprimer/retrouver ces valeurs
                        #rapidement (vitesse logarithmique). L'insertion se fait
                        #en regardant l'endroit où placer le nouveau node.
                        #Toutes ces opérations se font dans une priority_queue
                        #via make_heap, push_heap et pop_heap

COMPARAISON DES         #Voici (les vides indiquent que la fonctionnalité n'est 
CONTAINERS ==>          #pas disponible):

                          +----+----+----+----+----+----+----+----+----+----+
                          |VEC  DEQ  LIS  SET  MST  MAP  MMP  STK  QUE  PQU |
--------------------------+----+----+----+----+----+----+----+----+----+----+
access sequentiel         | ++ | +  |+++ | -- | -- | -- | -- |    |    |    |
access random (sans clef) | ++ | +  |    |    |    |    |    |    |    |    | 
access random (avec clef) |    |    |    | ++ | ++ | ++ | ++ |    |    |    |  
action en fonction d'un   |    |    |    |    |    |    |    |    |    |    | 
access random (avec clef) |    |    | +  | ++ | ++ | ++ | ++ |    |    |    | 
--------------------------+----+----+----+----+----+----+----+----+----+----+
Ajout/suppression fin     | ++ | +  | -  |    |    |    |    |+++ |+++ |    | 
Ajout/suppression milieu  | -- | -  | +  | ++ | ++ | ++ | ++ |    |    |    | 
Ajout/suppression début   | -- | ++ | +  |    |    |    |    |    |+++ |    | 
--------------------------+----+----+----+----+----+----+----+----+----+----+
Tri automatique           |    |    | -  | +  | +  | +  | +  |    |    |+++ | 
arithmétique pointeurs    | ++ |    |    |    |    |    |    |    |    |    | 
mémoire consommée         | ++ | +  | -  | -- | -- |--- |--- |+++ |+++ |+++ | 
--------------------------+----+----+----+----+----+----+----+----+----+----+

CONVERSION ENTRE        #Pour tous les containers entre eux dont :
CONTAINERS ==>          #  - les strings
                        #  - les istreams, les ostreams, les streambufs et leur
                        #    dérivés
                        #Mais à l'exception :
                        #  - des maps et multimaps
                        #  - des bitsets
                        #  - des container adaptors
                        #  - des valarrays
                        #Il suffit de construire l'un de ces containers avec un
                        #constructor prenant deux iterators (ou avec assign()
                        #pour les seq_cont), et d'utiliser deux iterators liés
                        #à un container d'un autre type.
                        #Exception : pour convertir un container vers un des
                        #streams (et non l'inverse), c'est impossible en une
                        #seule fois car les streams ne peuvent pas être 
                        #construits à partir d'iterators. Il faut donc faire :
                        #  - container -> string (cf ci-haut) -> stringstream
CONVERSION IMPOSSIBLES  #Cependant, pour les bitsets, on est obligé pour : 
OU DIFFICILES ==>       #  - le convertir en un autre container :
                        #     - le convertir en ULONG ou STRING, puis convertir
                        #       celui-ci vers le container.
                        #  - convertir un container en bitset :
                        #     - convertir ce container en ULONG ou STRING 
                        #       composée seulement de 1 et de 0
                        #Enfin, les maps, multimaps, container adaptors et
                        #valarrays ne permettent pas de conversion directe, on 
                        #est obligé de passer par une boucle et d'itérer tous 
                        #les éléments.

VITESSE ==>             #La vitesse des méthodes des containers peut être :
                        #  - constante :
                        #     - la plupart
                        #  - logarithmique :
                        #     - find, count, lower_bound, upper_bound, 
                        #       equal_range
                        #     - sort
                        #     - operator[] pour maps
                        #     - insert, erase pour associative containers
                        #  - linéaire :
                        #     - remove, remove_if, unique, merge, reverse
                        #     - reserve
                        #     - resize
                        #     - assign, operator=
                        #     - destructors, constructors
                        #     - insert, erase pour sequential containers (par
                        #       rapport aux éléments insérés ou supprimés pour 
                        #       tous + par rapport aux éléments déplacés pour
                        #       vector et deque

BAD_ALLOC ==>           #Certaines fonctions utilisent en interne l'allocator 
                        #pour faire un allocate(), ce qui peut lancer une 
                        #exception (bad_alloc dans le cas de l'allocator par 
                        #défaut) :
                        #  - CONTTT.resize()
                        #  - VECTOR.reserve()
                        #  - CONTTT.push_back()
                        #  - DEQ-LIST.push_front()
                        #  - CONTTT.insert()
                        #  - ADA_CONT.push()
                        #  - tous les constructors

                    /=+===============================+=\ 
                   /  :                               :  \    
                   )==:          SEQUENCE ET          :==(  
                   )==:     ASSOCIATIVE CONTAINERS    :==(   
                   \  :_______________________________:  /    
                    \=+===============================+=/ 

HEADER ==>              #<vector, deque, list, set, map>

a_s_cont(A_S_CONT)      #Copy constructor. A_S_CONT doit être du même type de
                        #container que a_s_cont.

A_S_CONT = A_S_CONT2    #Affecte A_S_CONT2 à A_S_CONT. A_S_CONT aura ensuite la 
                        #même taille et éléments que A_S_CONT2. A_S_CONT et 
                        #A_S_CONT2 doivent être du même type de container

a_s_cont<...>::iterator #Renvoie une classe (pas une instantiation) d'iterator 
                        #propre à a_s_cont, soit A_S_CONT_ITERATOR. A instantier
                        #puis initialiser ensuite avec une A_S_CONT_ITERATOR_VAR
                        #par exemple A_S_CONT.begin() ou A_S_CONT.end()
                        #Il s'agit de RANDOM_A_S_CONT_ITERATOR pour :
                        #  - vector, deque
                        #De BIDIRECTIONAL_A_S_CONT_ITERATOR pour :
                        #  - list
                        #Sauf pour vector<bool>, deque<bool> et list<bool>, qui
                        #renvoie juste un forward iterator (problème corrigé par
                        #Boost)
                        #Et de BIDIRECTIONAL_A_S_CONT_ITERATOR (sans les 
                        #opérations d'OUTPUT_A_S_CONT_ITRTR) pour :
                        #  - set, multiset
                        #Et de BIDIRECTIONAL_A_S_CONT_ITERATOR composé de deux
                        #membres first et second pour :
                        #  - map, multimap
                        #Ainsi BIDIRECTIONAL_A_S_CONT_ITERATOR->first et
                        #BIDIRECTIONAL_A_S_CONT_ITERATOR->second pointe vers les
                        #deux valeurs de la PAIR <const WVAR, WVAR2> pointée
                        #(first vers la clef, second vers la valeur de la clef)
a_s_cont<...>::         #Egal à reverse_iterator <a_s_cont<...>::iterator>
reverse_iterator        #Renvoie donc REVERSE_A_S_CONT_ITERATOR, à initialiser 
                        #avec une REVERSE_A_S_CONT_ITERATOR_VAR
a_s_cont<...>::         #Comme a_s_cont<...>::iterator, mais renvoie un const
const_iterator          #iterator
a_s_cont::              #Comme a_s_cont<...>::reverse_iterator, mais renvoie un 
const_reverse_iterator  #const iterator

a_s_cont<...>::size_type#Type de taille, souvent définie sous forme de size_t.
a_s_cont<...>::         #Type pour la différence entre deux pointeurs de 
difference_type         #l'itérateur du a_s_cont, souvent ptrdiff_t
a_s_cont<...>::
allocator_type          #Egal à ALLOCATOR
a_s_cont<...>::pointer  #Egal à ALLOCATOR::pointer
a_s_cont<...>::reference#Egal à ALLOCATOR::reference
a_s_cont<...>::
const_pointer           #Egal à ALLOCATOR::const_pointer
a_s_cont<...>::
const_reference         #Egal à ALLOCATOR::const_reference

A_S_CONT.begin()        #Renvoie un A_S_CONT_ITERATOR_VAR de type lié à 
                        #A_S_CONT, et placé sur son premier élément.
                        #Le fait qu'il soit random ou bidirectionnal dépend de
                        #ce qu'est a_s_cont<...>::iterator
A_S_CONT.end()          #Comme A_S_CONT.begin(), mais est placé sur l'élément 
                        #virtuel qui suit le dernier élément (sorte d'EOF). Il
                        #s'agit d'un élément ayant une valeur arbitraire 
                        #désignant l'EOF de manière interne à A_S_CONT.
A_S_CONT.rbegin()       #Renvoie un REVERSE_A_S_CONT_ITERATOR_VAR, lié à 
                        #A_S_CONT, et placé sur son dernier élément. Doit être 
                        #affecté à un ITERATOR_VAR de type RVERSE_A_S_CONT_ITRTR
A_S_CONT.rend()         #Comme A_S_CONT.rbegin(), mais placé sur l'élément 
                        #virtuel qui précède le premier élément (sorte de 
                        #reverse EOF).

A_S_CONT.size()         #Renvoie le nombre d'éléments de A_S_CONT (et non la 
                        #mémoire allouée), sous forme de SIZE_TYPE_VAL.
A_S_CONT.max_size()     #Renvoie le nombre d'éléments maximal pouvant être 
                        #contenu (et alloué au niveau de la mémoire) dans 
                        #A_S_CONT, sous forme de SIZE_TYPE_VAL.
A_S_CONT.empty()        #Retourne true si A_S_CONT est vide (A_S_CONT.size == 0)
                        #et false sinon.

A_S_CONT.clear()        #Le contenu de A_S_CONT devient vide (sa taille devient 
                        #0)
A_S_CONT.erase          #Supprime les éléments dans A_S_CONT contenus entre 
(A_S_CONT_ITRTR_VAR1    #A_S_CONT_ITRTR_VAR1 (inclus) et A_S_CONT_ITRTR_VAR2 
[, A_S_CONT_ITRTR_VAR2])#(exclus) (par défaut, l'élément qui suit).

A_S_CONT.swap(A_S_CONT2)#Echange le contenu de A_S_CONT et de A_S_CONT2 (doivent
                        #être du même type de container)

A_S_CONT.get_allocator()#Renvoie l'ALLOCATOR d'A_S_CONT.

HEADER ==>              #<vector, deque, list, set>

s_s_cont<..>::value_type#Egal à WVAR.

                    /=+===============================+=\ 
                   /  :                               :  \  
                   )==:      SEQUENCE CONTAINERS      :==(   
                   \  :_______________________________:  /    
                    \=+===============================+=/ 

HEADER ==>              #<vector, deque, list>

seq_cont([ALLOCATOR])   #Crée un SEQ_CONT vide, de taille 0, avec l'allocator
                        #ALLOCATOR (allocator <WVAR> par défaut). Il s'agit d'un
                        #explicit constructor.
seq_cont(SIZE_TYPE_VAL  #Crée un SEQ_CONT avec SIZE_TYPE_VAL éléments WVAR_VAL,
[, WVAR_VAL]            #avec l'allocator ALLOCATOR (allocator <WVAR> par 
[, ALLOCATOR])          #défaut). WVAR_VAL est par défaut, si WVAR fait 
                        #référence à :
                        #  - une classe WVAL : WVAL avec son constructor par 
                        #    défaut sans argument
                        #  - un type fondamental : 0
                        #Il s'agit d'un explicit constructor.
seq_cont                #Construit un SEQ_CONT avec les éléments allant de 
(TOU_CONT_INPT_ITRTR_   #TOU_CONT_INPUT_ITERATOR_VAR1 (inclus) à 
VAR1, TOU_CONT_INPUT_   #TOU_CONT_INPUT_ITERATOR_VAR2 (exclus). seq_cont et 
ITRTR_VAR2)             #TOU_CONT ne sont pas forcément du même type de 
                        #container.

SEQ_CONT.assign         #Equivaut à :
(SIZ_TYPE_VAL, WVAR_VAL)#  - SEQ_CONT = seq_cont<WVAR>(SIZE_TYPE_VAL, WVAR_VAL)
SEQ_CONT.assign         
(TOU_CONT_INPT_ITRTR    #Equivaut à :
_VAR1, TOU_CONT_INPUT_  #  - SEQ_CONT = seq_cont<WVAR>(TOU_CONT_INPT_ITRTR_VAR1,
ITRTR_VAR2)             #    TOU_CONT_INPT_ITRTR_VAR2)

SEQ_CONT.resize         #La taille de SEQ_CONT devient SIZE_TYPE_VAL. Si 
(SIZE_TYPE_VAL          #SEQ_CONT est tronqué, des éléments sont supprimés. Si 
[, WVAR_VAL])           #SEQ_CONT est rallongé, un flux de WVAR_VAL est ajouté à
                        #la fin de SEQ_CONT. Le WVAR_VAL par défaut est le même 
                        #que pour le constructor seq_cont(SIZE_TYPE_VAL ... ).

SEQ_CONT.front()        #Renvoie le premier élément de SEQ_CONT. Equivaut donc 
                        #à :
                        #  - SEQ_CONT[0]
SEQ_CONT.back()         #Renvoie le dernier élément de SEQ_CONT. Equivaut donc 
                        #à :
                        #  - SEQ_CONT[SEQ_CONT.size() - 1]

SEQ_CONT.insert         #Insert dans SEQ_CONT, à partir de sa position
(SEQ_CONT_RANDM_ITRTR   #SEQ_CONT_RANDOM_ITERATOR_VAR, SIZE_TYPE_VAL (par défaut
_VAR, [SIZE_TYPE_VAL],  #un) éléments WVAR_VAL, augmentant en conséquence la 
WVAR_VAL)               #taille de SEQ_CONT
                        #Si SIZE_TYPE_VAL est omis, un ITERATOR_VAR poitant sur
                        #l'élément inseré est renvoyé (sinon rien n'est renvoyé)
SEQ_CONT.insert         #Même chose, mais utilise les éléments du SEQ_CONT 
(SEQ_CONT_RANDM_ITRTR   #associé aux deux INPUT_ITERATOR_VAR à partir de 
_VAR, SEQ_CONT2_INPT_   #SEQ_CONT2_INPUT_ITRTR_VAR1 (inclus) jusqu'à
ITRTR_VAR1, SEQ_CONT2_  #SEQ_CONT2_INPUT_ITRTR_VAR2 (exclus). SEQ_CONT et 
INPT_ITRTR_VAR2)        #SEQ_CONT2 ne sont pas forcément le même type de 
                        #container.
SEQ_CONT.push_back      #Rajoute WVAR_VAL à la fin de SEQ_CONT. WVAR_VAL devient
(WVAR_VAL)              #donc le dernier élément de SEQ_CONT.
SEQ_CONT.pop_back()     #Supprime le dernier élément de SEQ_CONT.

HEADER ==>              #<vector, deque>

VEC-DEQ[SIZE_TYPE_VAL]  #Renvoie la référence (peut donc être une lvalue) de 
                        #l'élément numéro SIZE_TYPE_VAL de VEC-DEQ. Si 
                        #SIZE_TYPE_VAL est out of range, renvoie une référence 
                        #malgré le buffer overflow. Préférer VEC-DEQ.at()
VEC-DEQ.at(SIZ_TYPE_VAL)#Comme VEC-DEQ[SIZE_TYPE_VAL], mais lance une exception
                        #out_of_range si SIZE_TYPE_VAL > VEC-DEQ.size()

HEADER ==>              #<deque, list>

DEQ-LIST.push_front     #Rajoute WVAR_VAL au début de DEQ-LIST. WVAR_VAL devient
(WVAR_VAL)              #donc le premier élément de DEQ-LIST.
DEQ-LIST.pop_front()    #Supprime le premier élément de DEQ-LIST.

HEADER ==>              #<vector>

vector <WVAR, [ALOCATR]>#Classe de vector dont les éléments sont de type WVAR
                        #L'allocator est ALLOCATOR, allocator <WVAR> par défaut.
                        #Spécialisation si WVAR est bool :
                        #  - l'espace alloué aux BOOL_VAR devient 1 seul bit, et
                        #    non 1 octet
                        #  - les références renvoyées ne sont pas vraiment des
                        #    BOOL_VAR&, mais un type interne servant au 
                        #    mécanisme permettant de ne mettre que sur 1 bit

VECTOR.capacity()       #Renvoie le nombre d'éléments en mémoire alloués (et 
                        #non forcément utilisés) à VECTOR, sous forme de 
                        #SIZE_TYPE_VAL (>= à VECTOR.size()). Est augmenté à 
                        #chaque fois que VECTOR.size() augmente, mais le 
                        #contraire.
VECTOR.reserve          #Si VECTOR.capacity() est < SIZE_TYPE_VAL, alors la 
(SIZE_TYPE_VAL)         #mémoire allouée à VECTOR devient au moins SIZE_TYPE_VAL
                        #éléments.
                        #"Au moins" car cela peut être légèrement supérieur 
                        #pour arrondir à une taille préférée pour le buffer.
                        #La taille allouée est automatiquement augmentée si
                        #VECTOR.size() augmente, mais cela permet de ne le faire
                        #qu'une fois plutôt qu'à chaque changement de la taille,
                        #ce qui est plus performant.
                        #Comme la mémoire allouée peut changer de place pendant
                        #l'opération, tout précédent pointeur, référence ou 
                        #iterator sur VECTOR ne doit plus être utilisé.
                        #Si SIZE_TYPE_VAL > VECTOR.max_size(), une exception
                        #length_error est lancée.

HEADER ==>              #<deque>

deque <WVAR, [ALOCATR]> #Classe de deque dont les éléments sont de type WVAR
                        #L'allocator est ALLOCATOR, allocator <WVAR> par défaut.

HEADER ==>              #<list>

list <WVAR, [ALOCATR]>  #Classe de list dont les éléments sont de type WVAR

LIST.reverse()          #Inverse les éléments (leur ordre) dans LIST.
LIST.sort()             #Trie LIST. La comparaison entre chaque élément est
                        #effectuée via <.
LIST.sort(FONC_ADR)     #Même chose, mais n'utilise pas < mais un FONC_VAR
                        #personnalisée, prenant deux WVAR comme arguments et
                        #retournant bool. Pour un tri normal par exemple :
                        #  - bool FONC_VAR(WVAR WVAR_VAL1, WVAR WVAR_VAL2) {
                        #        return ( WVAR_VAL1 < WVAR_VAL2 );
                        #    }
LIST.remove_if(FONC_ADR)#Exécute FONC_VAR(WVAR) pour chaque élément de LIST, 
                        #soit pour chaque WVAR_VAL, et supprime cet élément si
                        #FONC_VAR return true.
                        #FONC_VAR doit être de type bool, et prendre un seul
                        #argument, du même type que WVAR.
LIST.remove(WVAR_VAL)   #Supprime tous les éléments de LIST dont la valeur est
                        #WVAR_VAL.
LIST.unique()           #Supprime tout élément dans LIST ayant la même valeur
                        #que l'élément qui le précède. LIST devrait donc être
                        #triée.
LIST.unique(FONC_ADR)   #Exécute FONC_VAR(WVAR_VAL1, WVAR_VAL2) pour chaque 
                        #élément de LIST (sauf le premier), où WVAR_VAL2 est 
                        #cet élément et WVAR_VAL1 celui qui le précède, et 
                        #supprime cet élément si FONC_VAR renvoie true (ce qui 
                        #fait que l'appel de FONC_VAR pour le prochain élément 
                        #gardera le même WVAR_VAL1)
LIST.merge(LIST2)       #Insert les éléments de LIST2 dans LIST. Chaque élément
                        #de LIST2 est traité l'un après l'autre, dans l'ordre.
                        #Un itérateur commence avant le premier élément de LIST 
                        #puis, pour chaque élément dans LIST2 :
                        #  - s'il est > à l'élément dans LIST, l'itérateur est 
                        #    avancé d'un élément, et l'élément dans LIST2
                        #    effectue une nouvelle boucle
                        #  - s'il est <= à l'élément dans LIST, l'élément de
                        #    LIST2 est placé avant cet élément. L'itérateur 
                        #    pointera donc sur le même élément. 
                        #  - si l'itérateur se trouve après le dernier élément
                        #    de LIST, les éléments de LIST2 restants sont placés
                        #    à la fin.
                        #Ainsi, il vaut mieux que LIST et LIST2 soient triés,
                        #ainsi merge() a pour effet d'insérer les éléments de
                        #LIST2 dans LIST, mais en suivant l'ordre numérique ou
                        #alphabétique.
LIST.merge(LIST2,       #Exécute FONC_VAR(WVAR_VAL1, WVAR_VAL2) pour chaque 
FONC_ADR)               #élément de LIST2, où WVAR_VAL1 est cet élément et 
                        #WVAR_VAL2 l'élément dans LIST1 à la position de 
                        #l'itérateur.
                        #A le même effet que ci-dessus, sauf que plutôt que de
                        #tester si WVAR_VAL1 <= WVAR_VAL2, on peut tester ce 
                        #qu'on veut.
                        #FONC_VAR renvoie un bool (true pour que l'élément soit
                        #inséré)
LIST.splice             #Insère LIST2 dans LIST_ITRTR_VAR avant son
(LIST_ITRTR_VAR, LIST2, #LIST_ITRTR_VAR. Si LIST2_ITRTR_VAR1 et LIST2_ITRTR_VAR2
[, LIST2_ITRTR_VAR1,    #sont précisés, ils délimitent (le premier inclus, le
LIST2_ITRTR_VAR2])      #second exclus) la partie de LIST2 à insérer. Dans tous
                        #les cas, les parties insérées sont supprimées de LIST2.
LIST.splice             
(LIST_ITRTR_VAR, LIST2, #Même chose, mais ne déplace que l'élément dans LIST2 se
LIST2_ITRTR_VAR1)       #trouvant à l'endroit désigné par LIST2_ITRTR_VAR1.

                    /=+===============================+=\ 
                   /  :                               :  \  
                   )==:    ASSOCIATIVE CONTAINERS     :==(   
                   \  :_______________________________:  /    
                    \=+===============================+=/ 

HEADER ==>              #<set, map>

ASS_CONT([PREDIC]       #Instantie un ASS_CONT vide. PREDIC est utilisé pour
[, ALLOCATOR])          #ordonner ASS_CONT (par défaut less<WVAR>()), et doit 
                        #être de type PREDIC_TYPE.
                        #Exemple :
                        # - ass_cont <WVAR, bool(*)(WVAR, WVAR)> 
                        #   ASS_CONT(FONC_ADR);
                        #L'allocator est ALLOCATOR, allocator <WVAR> par défaut.
                        #Il s'agit d'un explicit constructor.
ASS_CONT                #Même chose, mas ASS_CONT n'est pas vide, mais contient
(TOU_CONT2_INPT_ITRTR   #les valeurs contenues entre TOU_CONT2_INPUT_ITRTR_VAR1
_VAR1, TOU_CONT2_INPT_  #(inclus) et TOU_CONT2_INPUT_ITRTR_VAR2 (exclus). 
ITRTR_VAR2[, PREDIC]    #TOU_CONT et TOU_CONT2 ne sont pas forcément du même 
[, ALOCATOR])           #type de container pour les sets et multisets, mais 
                        #TOU_CONT2 doit être du même type si ASS_CONT est une 
                        #map ou une multimap
                        #Si ASS_CONT est un set ou un map, les doublons sont 
                        #supprimés avant d'enregistrer les valeurs.

ass_cont<...>::key_type #Type des clefs, soit WVAR.
ass_cont<...>::         #PREDIC_TYPE utilisé pour ordonner les clés du container
key_compare             #Par défaut less <WVAR>

ASS_CONT.key_comp()     #Renvoie une instantiation du fonctor ou une copie du 
                        #FONC_ADR utilisé pour comparer les clefs entre elles,
                        #de type ass_cont<...>::key_compare donc. Dépend donc de
                        #l'instantiation de ASS_CONT. Exemple :
                        #  - ASS_CONT.key_comp()(WVAR_VAL1, WVAR_VAL2)

ASS_CONT.lower_bound    #Renvoie un ASS_CONT_ITRTR_VAR pointant sur le premier
(WVAR_VAL)              #élément dans ASS_CONT étant >= WVAR_VAL, ou 
                        #ASS_CONT.end() si aucun élément dans ASS_CONT n'est >=
ASS_CONT.upper_bound    #Renvoie un ASS_CONT_ITRTR_VAR pointant sur le premier
(WVAR_VAL)              #élément dans ASS_CONT étant > WVAR_VAL, ou
                        #ASS_CONT.end() si aucun élément dans ASS_CONT n'est >
ASS_CONT.count(WVAR_VAL)#Renvoie le nombre de clefs dans ASS_CONT ayant pour 
                        #valeur WVAR_VAL. Ne peut donc être que 0 ou 1 s'il 
                        #s'agit d'un set ou d'une map.
ASS_CONT.equal_range    #Renvoie une PAIR <ass_cont<...>::iterator, 
(WVAR_VAL)              #ass_cont<...>::iterator> où :
                        #  - PAIR.first pointe la première clef avec la valeur 
                        #    WVAR_VAL trouvée dans ASS_CONT.
                        #  - PAIR.second pointe la clef suivant la dernière clef
                        #    avec la valeur WVAR_VAL trouvée dans ASS_CONT.
                        #Ainsi cela donne un range (PAIR.first inclus,
                        #PAIR.second exclus).
                        #Renvoie une paire avec deux fois le même itérateur si
                        #WVAR_VAL n'est pas trouvé : qu'importe sa valeur, ce 
                        #qui compte c'est que c'est un range vide (puisque
                        #PAIR.second est exclus).
ASS_CONT.find(WVAR_VAL) #Renvoie un ASS_CONT_ITRTR_VAR pointant vers l'un des 
                        #WVAR_VAL si ASS_CONT contient une clef de valeur 
                        #WVAR_VAL ou ASS_CONT.end() si une telle clef n'a pas 
                        #été trouvée.

ASS_CONT.erase(WVAR_VAL)#Supprime tous les éléments dans ASS_CONT dont la clef 
                        #vaut WVAR_VAL.

HEADER ==>              #<set>

set <WVAR[, PREDIC_TYPE]#Classe de set, dont les clés sont de type WVAR.
[, ALLOCATOR]>          #L'ordre dans set est effectué selon PREDIC. PREDIC est
                        #est une instantiation de PREDIC_TYPE (par défaut less 
                        #<WVAR>) s'il s'agit d'une classe.
                        #S'il s'agit d'une FONC_ADR, les SET devront être
                        #initialisées avec le constructor définissant un PREDIC
                        #de manière explicite, et PREDIC devra être de type
                        #PREDIC_TYPE
                        #Dans tous les cas, PREDIC_TYPE est de type bool, et
                        #prend deux WVAR_VAL comme argument.
                        #ALLOCATOR est par défaut allocator <WVAR>
multiset <WVAR[, PREDIC_#Comme set <...>, sauf qu'il s'agit de la classe de
TYPE][, ALLOCATOR]>     #multiset.

set_cont<...>::         
value_compare           #PREDIC_TYPE identique à set_cont<...>::key_compare

SET_CONT.value_comp()   #Comme ASS_CONT.key_comp(), mais pour les comparaisons
                        #entre les valeurs des clefs. Identique donc.

SET.insert(WVAR_VAL)    #Si aucune clef dans SET n'est == WVAR_VAL, insert
                        #WVAR_VAL dans SET (selon l'ordonnance de SET).
                        #Renvoie une PAIR <set<...>::iterator, bool> où :
                        #  - PAIR.first est un SET_ITRTR_VAR placé sur
                        #    l'élément WVAR_VAL inséré ou déjà existant
                        #  - PAIR.second est true si l'élément a été inséré, ou
                        #    false si un autre existait déjà.
SET.insert              #Même chose, sauf que :
(SET_ITRTR_VAR1,        #  - un SET2_ITRTR_VAR1 est donné comme indication
WVAR_VAL)               #    lorsqu'une valeur déjà existante de WVAR_VAL est
                        #    recherchée dans SET, si l'on pense qu'il pourrait
                        #    y en avoir une là (juste une question de
                        #    performance)
                        #  - seul le SET_ITRTR_VAR (placé sur l'élément
                        #    WVAR_VAL inséré ou déjà existant) est renvoyé.
SET.insert              #Insert les WVAR_VAL contenues entre SET2_ITRTR_VAR1
(SET2_ITRTR_VAR1,       #(inclus) et SET2_ITRTR_VAR2 (exclus) dans SET (sauf les
SET2_ITRTR_VAR2)        #WVAR_VAL dont il possède un doublon).
                        #SET et SET2 ne sont pas forcément du même type de
                        #container.

HEADER ==>              #<map>

map <WVAR, WVAR2        #Classe de map. Fonctionne comme la déclaration de set,
[, PREDIC_TYPE]         #sauf qu'il faut aussi déclarer une WVAR2 désignant le
[, ALLOCATOR]>          #type des valeurs de clefs.
multimap <WVAR, WVAR2   #
[, PREDIC_TYPE]         #Classe de multimap. Fonctionne comme la déclaration de 
[, ALLOCATOR]>          #map.

map_cont<...>::
mapped_type             #Type des valeurs des clefs, par défaut WVAR2.
map_cont<...>::
value_type              #Egal à pair <const WVAR, WVAR2>.

map_cont<...>::         #PREDIC_TYPE utilisé pour ordonner les valeurs des clefs
value_compare           #du container : BOOL_FONC_ADR(PAIR1<WVAR, WVAR2>, 
                        #PAIR2<WVAR, WVAR2>).

MAP_CONT.value_comp()   #Comme MAP_CONT.key_comp(), mais pour les comparaisons
                        #entre les valeurs des clefs. Est donc de type 
                        #ass_cont<...>::value_compare, soit :
                        #BOOL_FONC_ADR(PAIR1<WVAR, WVAR2>, PAIR2<WVAR, WVAR2>)
                        #Les éléments comparés sont PAIR1.second et PAIR2.second

MAP[WVAR_VAL]           #Renvoie une référence à la WVAR2_VAL de l'élément dont
                        #la clef est WVAR_VAL.
                        #Si cette clef n'existe pas, la crée, lui associe une
                        #valeur de clef en utilisant le constructor par défaut
                        #de WVAR2, puis renvoie une référence à la WVAR2_VAL
                        #nouvellement créée.

MAP.insert(...)         #Fonctionne comme insert() pour les sets, sauf qu'il ne
                        #s'agit pas des WVAR_VAL mais des PAIR<WVAR, WVAR2>

HEADER ==>              #<set, map>

MSET-MMAP.insert        #Insert WVAR_VAL dans MSET-MMAP (selon l'ordonnance de 
([MSET-MMAP_ITRTR_VAR1,]#MSET-MMAP).
WVAR_VAL)               #Renvoie un MSET-MMAP_ITRTR_VAR pointant sur le nouvel
                        #élément inséré.
                        #MSET-MMAP_ITRTR_VAR1 peut être donné comme une 
                        #indication de l'endroit (selon l'ordonnance de 
                        #MSET-MMAP) où WVAR_VAL1 risque d'être inséré (pour 
                        #améliorer les performances).
MSET-MMAP.insert        #Insert les WVAR_VAL contenues entre 
(MSET-MMAP2_ITRTR_VAR1, #MSET-MMAP2_ITRTR_VAR1 (inclus) et MSET-MMAP2_ITRTR_VAR2
MSET-MMAP2_ITRTR_VAR2)  #(exclus) dans MSET-MMAP. MSET-MMAP et MSET-MMAP2 ne 
                        #sont pas forcément du même type de container.

                    /=+===============================+=\ 
                   /  :                               :  \  
                   )==:      CONTAINER ADAPTORS       :==(   
                   \  :_______________________________:  /    
                    \=+===============================+=/ 

HEADER ==>              #<stack, queue>

ADA_CONT()              #Instantie un ADA_CONT vide.
ADA_CONT(ADA_CONT2)     #Copy constructor (doit être du même type de container)

ADA_CONT = ADA_CONT2    #Copy operator (doit être du même type de container)

ADA_CONT.size()         #Renvoie le nombre d'éléments de ADA_CONT
ADA_CONT.empty()        #Renvoie true si ADA_CONT est vide, c'est-à-dire si
                        #ADA_CONT.size() == 0

HEADER ==>              #<stack>

stack <WVAR[, seq_cont  #Classe de stack, basée sur le container seq_cont (par
<...>]>                 #défaut deque <WVAR>).

stack()                 #Instantie un stack vide
stack(SEQ_CONT)         #Instantie un stack ayant le même contenu que SEQ_CONT.
                        #SEQ_CONT doit être du même type que celui déclaré dans
                        #le template.

STACK.top()             #Renvoie une référence vers le dernier élément de STACK

STACK.push(WVAR_VAL)    #Rajoute un élément WVAR_VAL à la fin de STACK
STACK.pop()             #Supprime le dernier élément de STACK

HEADER ==>              #<queue>

queue <WVAR[, deq-list  #Classe de queue, basée sur le container deq-list (par
<...>]>                 #défaut deque <WVAR>).

queue()                 #Instantie un queue vide
queue(SEQ_CONT)         #Instantie un queue ayant le même contenu que SEQ_CONT
                        #SEQ_CONT doit être du même type que celui déclaré dans
                        #le template.

QUEUE.back()            #Renvoie une référence vers le dernier élément de QUEUE
QUEUE.front()           #Renvoie une référence vers le premier élément de QUEUE

QUEUE.push(WVAR_VAL)    #Rajoute un élément WVAR_VAL à la fin de QUEUE
QUEUE.pop()             #Supprime le premier élément de QUEUE

priority_queue<WVAR     #Classe de priority_queue, basée sur le container
[, vec-deq<...>         #vec-deq (par défaut vector <WVAR>). PREDIC_TYPE est
[, PREDIC_TYPE]]>       #similaire au PREDIC_TYPE des associative containers 
                        #(par défaut less <WVAR>)

priority_queue([PREDIC])#Instantie une pqueue vide, avec PREDIC pour ordonner 
                        #le heap (par défaut less<WVAR>())
priority_queue(PREDIC,  #Instantie une pqueue ayant le même contenu que SEQ_CONT
SEQ_CONT)               #SEQ_CONT doit être du même type que celui déclaré dans
                        #le template. Même chose pour PREDIC.
priority_queue          #Instantie une pqueue ayant le contenu allant de
(INPUT_ITERATOR_VAR1,   #INPUT_ITERATOR_VAR1 (inclus) à INPUT_ITERATOR_VAR2
INPUT_ITERATOR_VAR2     #(exclus). Ces itérateurs ne sont pas forcément du même
[, PREDIC[, SEQ_CONT]]) #type de container. Utilise make_heap pour ce faire.
                        #Même chose pour PREDIC.
                        #Si SEQ_CONT est spécifié, les éléments de SEQ_CONT sont
                        #également ajoutés. SEQ_CONT doit être du même type que 
                        #celui déclaré dans le template.

PQUEUE.top()            #Renvoie une référence vers le dernier élément de PQUEUE
                        #(qui doit donc être l'élément le plus grand)

PQUEUE.push(WVAR_VAL)   #Rajoute un élément WVAR_VAL dans PQUEUE en le triant
                        #via push_heap.
PQUEUE.pop()            #Supprime le dernier élément de PQUEUE (via pop_heap)