Remarques préliminaires :

• Tous les exercices de ce TP doivent être effectués dans le répertoire dirpile qui sera considéré comme répertoire courant.
• Rappel : Chemins d'accès aux sources des corrigés.

Sommaire

Pile générique implémentée par un tableau de taille fixe

exo_01

• Liste des fichiers créés ou modifiés : exo_01.cxx, CStackArray_01.h, CStackArray_01.hxx, Makefile_01

    Dans les fichiers CStackArray_01.h et CStackArray_01.hxx, écrire la classe CExcStackArray, de la même façon que les classes d'exceptions des différentes classes écrites dans le TP 10 (par exemple pour la classe CConteneur). Ajouter la classe générique CStackArray qui comporte :

• la constante CstCapacity, représentant la taille du tableau,
• un tableau de cette taille, d'éléments du type générique T,
• un destructeur virtuel vide,
• une implémentation des fonctions virtuelles pures clear(), Sommet(), Empiler() et Depiler().

    Dans le fichier exo_01.cxx, écrire la fonction Exo_01() qui teste les possibilités de la classe CStackArray. Essayer de lever les différentes exceptions possibles.

    Recopier le fichier Makefile_05 dans Makefile_01. Supprimer toutes les informations inutiles. Ajouter les dépendances dues aux fichiers de la classe CStackArray.

    Compiler et tester.

Corrigés :      exo_01.cxx      -      CStackArray_01.h      -      CStackArray_01.hxx      -      Makefile_01

Sommaire

Pile générique implémentée par un tableau de taille générique

exo_02

• Liste des fichiers créés ou modifiés : exo_02.cxx, CStackArray_02.h, CStackArray_02.hxx, Makefile_02

    Recopier les fichiers CStackArray_01.h et CStackArray_01.hxx respectivement dans CStackArray_02.hetCStackArray_02.hxx. Ajouter un second paramètre de généricité sous forme d'une constante non signée, avec une valeur par défaut.

    Recopier le fichier exo_01.cxx dans exo_02.cxx. Modifier la déclaration de la pile.

    Recopier le fichier Makefile_01 dans Makefile_02. Ajouter les dépendances dues aux nouveaux fichiers de la classe CStackArray.

    Compiler et tester.

Corrigés :      exo_02.cxx      -      CStackArray_02.h      -      CStackArray_02.hxx      -      Makefile_02

Sommaire

Pile générique implémentée par un tableau dynamique de taille fixe

exo_03

• Liste des fichiers créés ou modifiés : exo_03.cxx, CStackArray_03.h, CStackArray_03.hxx, Makefile_03

    Recopier les fichiers CStackArray_02.h et CStackArray_02.hxx respectivement dans CStackArray_03.h et CStackArray_03.hxx. Supprimer le second paramètre de généricité.

    Dans la classe CStackArray :

• remplacer le tableau d'éléments de type T par un pointeur d'éléments,
• ajouter un constructeur, dont le paramètre représente la taille maximale de la pile, avec une valeur par défaut afin de conserver au maximum la compatibilité avec le code déjà écrit par les utilisateurs. Il est possible que l'allocation mémoire échoue, c'est pourquoi il faut :
  • ajouter la constante CstMemInsuff dans la classe CStackArray,
  • indiquer que le constructeur peut lever une exception CExcStackArray,
• ajouter la donnée membre m_capacity, afin de mémoriser la taille du vecteur,
• ajouter au destructeur virtuel la libération de l'espace mémoire du tableau,
• implémenter toutes les fonctions.

Remarque :

La classe CStackArray contient maintenant un pointeur. Le constructeur par copie et l'affectation standard ne peuvent plus être utilisés car ils ne dupliquent que les données membres directement contenues dans l'objet, mais pas les parties "externes" pointées. Dans cette version, on se contentera d'interdire ces deux fonction.

    Recopier le fichier exo_02.cxx dans exo_03.cxx. Modifier la création de la pile.

    Recopier le fichier Makefile_02 dans Makefile_03. Ajouter les dépendances dues aux nouveaux fichiers de la classe CStackArray.

    Compiler et tester.

Corrigés :      exo_03.cxx      -      CStackArray_03.h      -      CStackArray_03.hxx      -      Makefile_03

Sommaire

Pile générique implémentée par un tableau dynamique de taille variable

exo_04

• Liste des fichiers créés ou modifiés : exo_04.cxx, CStackArray_04.h, CStackArray_04.hxx, Makefile_04

Attention : plusieurs méthodes de la classe CStackArray sont susceptibles d'échouer. S'il s'agit de constructeur(s), l'objet n'est pas construit. Dans le cas général d'un échec de constructeur, il faut s'assurer qu'aucune allocation mémoire n'a été effectuée avant cet échec, ou qu'elle a été libérée avant la sortie du constructeur. En effet, le destructeur ne sera jamais appelé. Dans le cas d'une autre méthode, il faut s'assurer que l'objet récupéré par l'utilisateur n'est pas modifié par la méthode.

Remarque : il est brutal de lever une exception dès que la taille du vecteur ne peut pas être doublée. En effet, il est peut-être possible d'augmenter la taille de 50%, ou 25%, etc., ou seulement d'un seul élément. On peut donc faire des tentatives d'allongement de plus en plus réduites, jusqu'à n'essayer d'ajouter qu'un seul élément.

    Pour rendre notre classe encore plus souple, les deux dernières possibilités pourraient être réunies : une taille non nulle passée en paramètre serait une taille fixe, une taille nulle signifierait une taille modifiable automatiquement selon les besoins à partir d'une valeur initiale par défaut. D'autres paramètres pourraient être ajoutés ultérieurement, à condition qu'ils aient tous des valeurs par défaut, indiquant la valeur de l'incrément, si la taille est fixe ou adaptable, etc.

    Lorsque l'utilisateur veut empiler et que le tableau est plein, il est proposé de doubler la taille du tableau. Cela nécessite de conserver la taille courante du vecteur, dans une nouvelle donnée membre m_capacity.

    Une donnée membre étant un pointeur, il est nécessaire d'interdire provisoirement le constructeur par copie et l'affectation. Ces deux fonctions seront implémentées dans le prochain exercice.

    Il est logique de penser que, puisque la taille du vecteur est augmentée chaque fois que le vecteur est plein, elle devrait aussi être réduite lorsque la pile se vide. On pourrait par exemple diviser la taille du vecteur par deux chaque fois qu'il est à plus de la moitié vide. Ce serait une très mauvaise idée car, dans le cas où une succession d'empilement et de dépilement se produirait autour de cette taille critique, le conteneur passerait la majorité de son temps à allouer/désallouer et recopier le vecteur. Une telle solution nécessiterait un mécanisme "d'amortissement".

    Nous adopterons ici la solution utilisée dans de nombreuses bibliothèques, consistant à ne réduire la taille du vecteur qu'à la demande, en ajoutant au conteneur CStackArray la fonction resize() dont le paramètre indique la nouvelle taille du vecteur. Quatre cas doivent être envisagés :

• la nouvelle taille est supérieure à la taille courante : le vecteur est allongé,
• la nouvelle taille est égale à la taille courante : le vecteur est inchangé,
• la nouvelle taille est inférieure à la taille du vecteur, mais supérieure au nombre d'éléments : la taille du vecteur est réduite à la taille demandée,
• la nouvelle taille est inférieure au nombre d'éléments : il est prudent de ne pas tronquer la pile et de ramener la taille du vecteur au nombre d'éléments.

    Un inconvénient très pervers de la réduction de la taille du vecteur, automatique ou volontaire, peut apparaître lorsque le conteneur alloue un vecteur de taille réduite au moyen de l'opérateur new. Il peut en effet arriver, à cet instant, que la mémoire libre soit insuffisante, et qu'une exception bad_alloc soit levée : la libération de la mémoire échoue par manque de mémoire !!! Il convient, dans ce cas, de ne pas redimensionner. Les conteneurs standard offrent une fonction supplémentaire, capacity(), qui permet de connaître le taux d'occupation de la mémoire qui peut être défini par : size() / capacity() * 100 %. Ajouter la fonction capacity() à la classe CStackArray.

    Recopier les fichiers CStackArray_03.h et CStackArray_03.hxx respectivement dans CStackArray_04.h et CStackArray_04.hxx. Que ce soit pour la fonction Empiler() ou pour la fonction resize(), la même séquence doit être répétée :

• essayer d'allouer l'espace mémoire nécessaire,
• si l'allocation réussit, recopier l'ancien vecteur dans le nouveau,
• libérer l'ancien vecteur,
• rediriger le pointeur de l'ancien vecteur vers le nouveau,
• modifier la donnée membre m_capacity.

    A la classe CStackArray ajouter la fonction privée Realloc() de profil :
 

void Realloc (int Increment) throw (std::bad_alloc);

où Increment est la valeur algébrique de l'augmentation de taille du tableau, et dont le comportement est décrit ci-dessus.

    Modifier la fonction Empiler() pour gérer l'augmentation automatique du tableau décrite dans la remarque en utilisant la fonction Realloc().

    Ajouter la fonction resize() de profil :
 

void resize (unsigned NewSize) throw (CExcStackArray);

où NewSize est la nouvelle taille du tableau, conformément aux indications ci-dessus.

    Recopier le fichier Makefile_03 dans Makefile_04, et ajouter les dépendances dues aux fichiers CStackArray_04.*. Vous pouvez recopier le fichier de test exo_04.cxx, disponible dans les corrigés.

    Compiler et tester.

Corrigés :      exo_04.cxx      -      CStackArray_04.h      -      CStackArray_04.hxx      -      Makefile_04

Sommaire

Constructeur par copie et affectation

exo_05

• Liste des fichiers créés ou modifiés : exo_05.cxx, CStackArray_05.h, CStackArray_05.hxx, Makefile_05

• soit d'interdire ces deux opérations, en déclarant ces fonctions dans la partie privée de la classe CStackArray, ce que nous avons fait jusqu'à présent,
• soit de les implémenter correctement. C'est l'objet de cet exercice.

    Recopier les fichiers CStackArray_04.h et CStackArray_04.hxx respectivement dans CStackArray_05.h et CStackArray_05.hxx. Faire passer les déclarations des deux fonctions de la partie privée dans la partie publique et les implémenter. Si la capacité de la pile réceptrice est suffisante pour recevoir les éléments de la pile émettrice, il n'est pas nécessaire de la redimensionner à la taille exacte nécessaire. L'utilisateur peut, s'il le souhaite, effectuer cette opération, grâce aux fonctions capacity() et resize().

    Les deux méthodes sont très semblables. On peut donc écrire le constructeur par copie en utilisant "astucieusement" l'opérateur d'affectation.

    Recopier le fichier Makefile_04 dans Makefile_05, et ajouter les dépendances dues aux fichiers CStackArray_05.*.

    Recopier le fichier exo_04.cxx dans exo_05.cxx en supprimant les parties inutiles, et en testant les deux nouvelles méthodes.

    Compiler et tester.

Corrigés :      exo_05.cxx      -      CStackArray_05.h      -      CStackArray_05.hxx      -      Makefile_05

Sommaire

Classe standard stack

exo_06

• Liste des fichiers créés ou modifiés : exo_06.cxx,

• le type des objets à empiler,
• la nature du conteneur qui sert à implémenter la pile.

    Compiler et tester.

Corrigés :      exo_06.cxx

Sommaire

Téléchargement des corrigés :

Chemins d'accès aux sources des corrigés :

© D. Mathieu     mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique