Les conteneurs de la STL

But : Donner un aperçu rapide des conteneurs de la STL à travers un résumé du cours de Bruno Garcia.

[modifier] Introduction

La librairie standard du C++ (STL en anglais) est née de la volonté d'apporter aux programmeurs C++, un canevas de programmation efficace, générique et simple à utiliser.

Celui-ci comprend :

• Des classes de conteneurs génériques et des algorithmes associés
• Une classe string paramétrée par le type de caractères qu'elle contient
• Une nouvelle famille de classes de flux.

Dans cet article nous allons nous intéresser uniquement aux classes conteneurs. Il s'agit en fait d'un résumé de l'excellent cours de Bruno Garcia dont le lien figure à la fin de cet article.

Bonne lecture !

[modifier] Spécificité de la STL

Tout d'abord, les fichiers d'entête de la STL n'ont pas d'extension .h en fin de nom. Par exemple, pour inclure le fichier d'entête pour la classe list, il faut écrire #include <list>.

D'autre part, la STL utilise la notion d'espace de nommage qui peut s'apparenter à la notion de paquetage. Ainsi, toutes les classes de la STL sont regroupées au sein d'un espace de nommage std.

L'utilisation de cet espace de nommage peut se faire de 3 façons :

• Soit faire précéder chaque utilisation d'objets STL par std::nomdeclasse,
• Soit faire une déclaration using pour les objets trop souvent usités, par exemple using std::cout;,
• Soit indiquer l'utilisation de l'espace de nommage par la directive using namespace std;

Je conseille plutôt la première ou la deuxième solution pour éviter les conflits avec d'autres espace de nommage qui pourrait contenir des classes du même nom. Utiliser une directive using sur un namespace est idiot car cela ruine totalement la raison même de l'existence du concept de namespaces.

[modifier] Les conteneurs

[modifier] La classe vector

Les vecteurs de la STL sont tout à fait semblables aux tableaux que l'on a l'habitude de manipuler en C++. Ils sont néanmoins encapsulés dans des classes pour leur fournir des capacités supplémentaires, en particulier, la croissance dynamique.

Leurs principales caractéristiques sont les suivantes :

• Accès indexé aux éléments en O(1)
• Ajout ou suppression d'un élément à la fin du vecteur sans redimensionnement en O(1)
• Ajout ou suppression d'un élément à la fin du vecteur avec redimensionnement en O(n)
• Ajout ou suppression d'un élément à la fin du vecteur en O(1) amorti
• Ajout ou suppression d'un élément au milieu du vecteur en O(n) où n est la taille du vecteur.

Il convient de mettre un bémol concernant l'ajout d'un élément à la fin d'un vecteur. En effet, les vecteurs sont à croissance dynamique. Autrement dit, si vous décidez d'ajouter un élément dans un vecteur déjà plein à l'aide de la méthode push_back, celui-ci sera agrandi, ce qui nécessite trois opérations :

• Allocation d'un nouveau vecteur
• Recopie des éléments depuis l'ancien vecteur vers le nouveau
• Suppression de l'ancien vecteur

Or, ces opérations peuvent être coûteuses, au pire en O(n). Se pose également la question du choix de la future taille. Andrew Koenig nous explique que la technique la plus efficace consiste à utiliser un redimensionnement exponentiel i.e. à chaque réallocation, la taille du vecteur est multipliée par un facteur (1 + a) où a est un nombre strictement positif. Ainsi, plus le vecteur devient grand, plus il s'agrandira rapidement.

Cette stratégie a l'avantage de rendre les redimensionnement de moins en moins fréquents au détriment d'un encombrement parfois exagéré de la mémoire. Du fait de la fréquence faible des redimensionnements, on peut considérer que la complexité asymptotique (ou amortie) de l'opération d'ajout d'un élément en bout de tableau est en O(1).

Il existe une alternative à std::vector, par la communauté GCN, la classe : SecureArray

[modifier] La classe deque

Les DQ sont la séquence élémentaire la plus délicate à cerner car intermédiaire entre une liste et un vecteur.

• Elle est très efficace dès lors qu'il s'agit d'ajouter ou de retirer une valeur à l'une de ses extrémités.
• Elle possède un opérateur d'indexation de complexité o(log(n)) amortie
• Les insertions en milieu de séquence sont plus rapides que sur un vecteur sans pour autant atteindre le niveau de performances des listes.

[modifier] La classe list

Elles modélisent le type liste chaînée habituel. Contrairement aux vecteurs, elles ne possèdent pas d'opérateur d'indexation mais permettent d'ajouter ou de supprimer un élément à n'importe quelle position en O(1).

Bien qu'il n'y ait jamais de place morte dans une liste mais, du fait de la structure de chaîne, l'occupation en mémoire d'une liste est le plus souvent supérieure (mais très peu) à celle d'un vecteur pour le même nombre d'éléments stockés.

[modifier] La classe stack

Les piles sont associées au modèle d'accès aux données dernier arrivé premier sorti. En d'autres termes, le dernier élément à être entré dans la pile sera le premier utilisé. Le modèle tire son nom de l'analogie avec une pile d'assiette où l'on accède toujours au même élément : celui du dessus que ce soit par empilage ou dépilage.

Il est possible de baser une pile sur tous les types de structures élémentaires. On notera toutefois qu'utiliser une liste s'avère peu judicieux car l'on accède qu'à l'élément final. Aussi on se limitera aux vecteurs et aux DQ.

A l'instar des files, les piles n'ont qu'un constructeur par défaut, il n'est pas possible d'obtenir d'itérateurs sur les piles, et le type des éléments que vous souhaitez loger dans une pile doit supporter les opérations == et <=.

[modifier] La classe queue

Les files sont associées au modèle d'accès premier arrivé, premier traité, à l'image, par exemple, d'une file d'attente à un guichet. Les opérations offertes sont très limitées car elles permettent d'ajouter un élément à la fin, consulter l'élément présent à chaque bout, retirer l'élément en tête de file.

Deux particularités notables sur les files :

• elles ne possèdent pas d'autre constructeur que celui par défaut (sans argument)
• afin de fonctionner correctement, les opérations == et <= sont requises sur le type T des éléments que l'on souhaite placer dans la file.

Les files, effectuant des accès fréquents aux deux extrémités de la structure de donnée sous-jacente, ne doivent pas être construites sur un vecteur (le retrait d'un élément en tête serait trop lent) mais plutôt sur une liste ou une DQ. Toutefois, il est conseillé d'utiliser une DQ qui offre de meilleurs temps de réponse pour les opérations d'ajout et de suppression aux deux extrémités. D'ailleurs, si votre compilateur accepte les template avec valeur par défaut, la construction se fait automatiquement sur une DQ.

[modifier] La classe priority_queue

Les files à priorité (ou tas) sont des collections ordonnées d'éléments qui ne donnent accès qu'à un seul élément : le plus prioritaire. La priorité est déterminée en fonction d'un prédicat passé au constructeur de la structure.

Les utilisations des files à priorité sont multiples. Citons par exemple l'ordonnancement des processus dans un système d'exploitation. L'algorithme du tri en tas peut être divisé en deux phases : construction d'un tas puis extraction du meilleur élément tant que le tas n'est pas vide.

Les files à priorité doivent être basées sur une structure indexée ... ce qui élimine les listes d'entrée de jeu ! Si l'occupation mémoire n'est pas votre soucis majeur, vous aurez intérêt à choisir une DQ qui autorise des opérations plus rapides.

[modifier] Conclusion

Voilà, cet article est déjà terminé. Comme je l'ai dit au départ, ce n'est pas véritablement un article mais plutôt un résumé du cours de bruno Garcia pour vous donner envie d'aller plus loin dans l'étude de la STL. Cette librairie offre d'énormes avantages alors autant en profiter ;). Comme promis, voilà le lien vers le cours de bruno Garcia : [1]. Il se trouve aussi dans l'archive associée.