Table of Contents
Les containers dans la STL
Dans la STL est appellé “container” une classe qui stocke plusieurs éléments d'un même type.
La philosophie derrière les containeurs
L'objectif est de fournir une interface commune à l'ensemble des classes qui propose de stocker une collection d'éléments d'un type donné. Cette uniformisation passe par certaines règles de fonctionnement.
Règle n°1 : Le containeur est responsable de l'allocation de la mémoire pour stocker les données dans le containeur.
Quand on ajoute un élément à un containeur, le containeur va créer la mémoire nécessaire pour stocker l'objet et va recopier l'objet passé dans ce nouvel emplacement mémoire en utilisation le constructeur ou l'opérateur de recopie.
Quand on détruit un élément du containeur, l'objet est détruit et son constructeur est appelé.
Enfin, cette règle a une conséquence importante, quand le containeur est détruit, tous les éléments qui sont dans le containeur sont détruits.
Naturellement, les informations relatifs au type des éléments stockés dans un containeur est fournir par une interface normalisée :
value_type | Le type des éléments stockés dans le containeur |
reference | Le type référence permettant d'accéder aux éléments stockés dans le containeur en écriture |
const_reference | Le type référence permettant d'accéder aux éléments stockés dans le containeur en lecture |
size_type | Le type permettant de représenter la taille du containeur |
Règle n°2 : Chaque containeur offre la possibilité d'énumérer l'ensemble des éléments stockés dans le containeur sans avoir à connaitre les détails d'implantation du containeur.
Cette énumération s'effectue en parcourant la structure interne en utilisant (des itérateurs). Chaque collection va offrir les méthodes suivantes :
begin() | retourne un itérateur sur le premier élément situé dans le containeur . |
end() | retourne un itérateur indiquant la fin de l'énumeration. |
rbegin() | retourne un itérateur sur le dernier élément situé dans le containeur pour énumérer les élément en débutant par le dernier élément de la collection. |
rend() | retourne un itérateur indiquant la fin de l'énumeration débutant par le dernier élément situé dans le containeur. |
Naturellement, on fournit aussi les types des itérateurs :
iterator | Le type d'un itérateur permettant d'énumérer les éléments stockés dans le containeur et fournissant un accès en lecture et en écriture aux éléments stockés dans le containeur. |
const_iterator | Le type d'un itérateur permettant d'énumérer les éléments stockés dans le containeur et fournissant un accès en lecture aux éléments stockés dans le containeur. |
Nous retrouvons parmi les classes containers de la STL l'ensemble des structure de données habituelles correspondant à des séquences d'éléments ou au contraire des dictionnaires.
Règle n°3 : Les fonctions propres à l'implantation des containeurs sont fournies par chacun des containeurs.
Typiquement, les containeurs qui correspondent à des tableaux vont proposer des fonctions d'accès par index. Ainsi, les containeurs ''std::array'' ''std::vector'' vont offrir les fonctions suivantes :
reference operator [] (int) | Accès par indexation équivalente à l'accès au ième élément d'un tableau |
Comme le containeur vector supporte l'insertion d'éléments, des méthodes propres sont disponibles :
| push_back(const value_type&) | Ajoute un élément à la fin du vecteur |
| pop_back() | Enlève l'élément situé à la fin du vecteur |
De manière similaire, pour les ensembles set, des méthodes complémentaires sont disponibles pour gérer insérer des éléments :
| insert(const value_type&) | Ajoute un élément à l'ensemble d'éléments. |
Règle n°4 : Utiliser un itérateur pour identifier un élément stocké dans un containeur
La plupart des méthodes qui nécessite d'identifier un élément stocké à l'intérieur d'un containeur suppose que l'élément soit référencé par un itérateur.
Ainsi pour supprimer un élément d'un ensemble set, nous appelons la méthode erase qui prend un itérateur qui fait référence à l'élément à supprimer.
erase(iterator) | Supprime l'élément référence par l'itérateur. |
Ceci est aussi le cas pour l'ajout d'un élément dans un vecteur vecteur :
emplace(const_iterator, Args&& …) | Ajoute un élément après l'élément identifié par l'itérateur passé en argument. |
De même, quand nous recherchons un élément dans une structure, la fonction retourne un itérateur qui fait référence à l'élément qui est stocké dans la structure. Pour exemple, la fonction find qui recherche si un élément est présent dans un ensemble set :
const_iterator find(const value_type&) | Recherche un élément dans l'ensmble et retourne un itérateur qui fait référence à l'élément trouvé ou au contraire retourne l'itéateur retourné par end() pour indiquer que l'élément n'est pas présent dans l'ensemble. |
Les containers par type
- Séquence d'éléments
array un tableau statique (de taille fixe).
vector un tableau dynamique (de taille variable).
vector une structure permettant l'insertion ou la suppression rapide des éléments soit au début soit à la fin de la séquence.
forward_list une liste simplement chaînée.
list une liste doublement chaînée.
- Les séquences d'éléments ordonnés
Dans ce cas, les éléments stockés dans la structure sont ordonnés. L'énumération des éléments dans ce cas retourne les éléments en débutant par le plus petit et allant jusqu'au plus grand.
set un ensemble d'éléments ordonnés.
map un dictionnaire dont les éléments sont référencés et ordonnées par rapport à une clé qui identifie chaque élément. Cette structure supporte plusieurs occurences d'un même élément.
multiset un ensemble d'éléments ordonnés.
multimap un dictionnaire dont les éléments sont référencés et ordonnées par rapport à une clé qui identifie chaque élément. Cette structure supporte plusieurs occurences d'un même élément.
- Les séquences d'éléments non-ordonnés
Dans ce cas, les éléments stockés dans la structure ne sont pas ordonnés. L'énumération des éléments dans ce cas retourne les éléments dans un ordre arbitraire dépendant de l'implantation. Les implantations standards utilisent des fonctions de hashages pour générer offrir un accès rapide aux données.
unordered_set un ensemble d'éléments ordonnés.
unordered_map un dictionnaire dont les éléments sont référencés et ordonnées par rapport à une clé qui identifie chaque élément. Cette structure supporte plusieurs occurences d'un même élément.
unordered_multiset un ensemble d'éléments ordonnés.
unordered_multimap un dictionnaire dont les éléments sont référencés et ordonnées par rapport à une clé qui identifie chaque élément. Cette structure supporte plusieurs occurences d'un même élément.
- Les adaptateurs
Un adaptateur fournit une surcouche qui ajouter à un containeur gérant des sequences d'éléments une interface pour utiliser cette structure comme une pile, une queue ou une queue avec priorité.
stack offre une interface de type pile (structure LIFO).
queue offre une interface de type queue (structure FIFO).
priority_queue offre une interface de type queue avec priorité.
