Les conteneurs
Les conteneurs sont la notion qui a fait connaître et qui a permis de
genéraliser l'utilisation de la STL.
Il s'agit d'un ensemble d'implémentations d'objets de stockage, avec
les opérations de bases que l'on peut effectuer dessus.
dessus.
Les conteneurs sont les objets les plus couramment utilisés en programmation.
Nous avons perpétuellement besoin de ce type d'objets. J'avoue qu'avant
de connaitre la STL, je passais mon temps à réécrire des
listes ou des implémentations de vecteurs, pour chacun des types d'objets
que je créais. Un jour j'en ai eu marre et je me suis penché sur
les notions de généricité avant de découvrir la
STL:
- l'implémentation fonctionne pour n'importe quel type d'objet, du plus
simple au plus complexe
- Il n'y a pas de problèmes d'accès aux éléments
( si vous avez déjà créé une liste vous voyez de
quoi je parle ... )
- les insertions , suppressions sont gérées de manière
efficace
- la gestion des allocations, désallocations est automatique ( avec des
pools d'objets libres par exets libres par exemple )
Pour résumer : il n'y a plus de prise de tête!
Deux grandes classes de conteneurs sont distinguables, auxquelles on peut associer
un ensemble de conteneurs dérivés:
- les conteneurs de séquence
Vecteurs, listes, et deques- les conteneurs associatifs
Sets et multisets, maps et multimaps- les conteneurs dérivés
Stack, queue et priority_queue
|
Tableau classique
|
Vector
|
list
|
Deque
|
|
|
Inserer/effacer au début
|
n/a
|
linéaire
|
constant
|
constant
|
constant
|
Inserer/effacer à la fin
|
n/a
|
constant
|
constant
|
constant
|
|
Inserer/effacer n'importe où
|
n/a
|
linéaire
|
constant
|
linéaire
|
|
Accès au premier élémenave;s au premier élément
|
constant
|
constant
|
constant
|
constant
|
|
Accès au dernier élément
|
constant
|
constant
|
constant
|
constant
|
|
Accès n'importe où
|
constant
|
="center">constant
constant
|
linéaire
|
constant
|
- opérateur ()ockquote> - opérateur () : T();
- constructeur par recopie : T(const T&);
- destructeur : ~T();
- opérateur d'affectation : T& operator=(const T&);
- opérateur () : T();
- constructeur par recopie : T(const T&);
- destructeur : ~T();
- opérateur d'affectation : T& operator=(const T&);
- opérateur &() : T* operator&();
- opérateur de comparaison < : int operator < (const T&, const T&);
- opérateur d'égalité : int operator==(const T&, const T&);
- opérateur () : T();
- constructeur par recopie : T(const T&);
- destructeur : ~T();
- opérateur d'affectation : T& operator=(const T&);
- le set ( l'ensemble ) : chaque élément est sa propre clé et doit donc être unique.
- le multiset, qui est l'équivalent d'un l'équivalent d'un set, mais permettant les doublons
- la map : chaque élément est associé à une clé ( c'est épatant non! ).
- la multimap, équivalente à la map, mais qui permet plusieurs éléments pour une même clé
- la stack ( pile )
La pile offre simplement la possibilité d'ajouter et supprimer à la fin.
Le plus efficace est donc de l'utiliser avec un vecteur, mais elle peut aussi être utilisée avec la deque et la liste ( qui serait un très iste ( qui serait un très mauvais choix! )
- la queue ( file )
Permet d'ajouter à la fin et de retirer au début
A utiliser avec la deque ou la liste. Le vecteur fonctionne, mais attention les performances!
- la priority-queue ( file avec priorité )
Rien à dire, le nom est explicite
La déclaration peut prendre en paramêtre une fonction de comparaison pour les priorités
A utiliser avec un vecteur ou a la limite avec une deque si la taille est très variable. La liste est inutilisable car l'opérateur [] doit être défini
| << Précédent |