Remarques préliminaires :

• Tous les exercices de ce TP doivent être effectués dans le répertoire dirliste qui sera considéré comme répertoire courant.
• Nous avons étudié précédemment la "structure de données" appelée "liste doublement chaînée" ou plus simplement "liste double". Nous en avons montré l'utilisation pour implémenter différents conteneurs simples. Tous ces conteneurs partagent la même organisation des informations (même "structure de données") pour implémenter des comportements très différents. Tous les conteneurs étudiés jusqu'à présent (piles, fifos, deques), peuvent contenir de multiples informations mais un seul élément (ou deux pour les deques) est directement accessible à un instant donné, tous les autres étant masqués jusqu'à ce qu'il soit prélevé. D'autres conteneurs au contraire permettent l'accès à tous leurs éléments sans qu'il soit nécessaire de les prélever. C'est le cas des vecteurs et des conteneurs listes. Ils se différencient par les propriétés suivantes :
  • l'accès aux éléments d'un vecteur est dit "aléatoire", ce qui signifie qu'à tout moment, n'importe quel élément peut être accédé en temps constant (c'est-à-dire indépendant du rang de l'élément). L'implémentation naturelle d'un vecteur est un tableau. Si la suppression et l'insertion en fin de vecteur est immédiate, au contraire ces opérations à l'intérieur du vecteur sont d'autant plus coûteuses qu'elles sont proches du début du vecteur. On dit que leur coût est linéaire puisque le nombre d'éléments à décaler est proportionnel à l'éloignement de la position d'insertion par rapport à la fin du vecteur.
  • l'accès aux éléments d'une liste est dit "séquentiel", ce qui signifie qu'à tout moment, seul l'élément courant et les éléments qui l'encadrent sont directement accessibles. L'accès à n'importe quel élément est possible, mais en temps linéaire (c'est-à-dire proportionnel à son rang par rapport à l'élément courant), puisqu'il faut parcourir tous les éléments qui l'en séparent avant de l'atteindre. L'implémentation naturelle d'un conteneur liste est une structure de données "liste chaînée". Les opérations d'insertion/suppression sont en temps constant puisque, comme nous l'avons vu lors de l'écriture de la classe CLink2Gen, elles ne concernent que les éléments précédent et suivant.
  • On trouvera quelques informations générales concernant la signification de la complexité des opérations sur les conteneurs dans le document SGI : STL Complexity Specifications.
• Il existe trois façons de parcourir les différents éléments d'un conteneur tel qu'une liste ou un vecteur :
  • le conteneur gère une donnée membre privée m_Courant qui pointe sur l'élément courant, et offre différentes méthodes parmi lesquelles :
    • Debut() qui positionne le pointeur courant sur le premier élément du conteneur,
    • Suivant() et Precedent() qui font progresser le pointeur interne m_Courant vers la queue ou vers la tête,
    • les prédicats EstEnDebut() ou EstEnFin(), vrais lorsque le pointeur courant est sur l'une des extrémités,
    • l'accesseur GetElem() qui renvoie l'information contenue dans l'élément courant.
    Cette méthode est très limitée car il ne peut y avoir en même temps qu'un seul pointeur courant sur le conteneur, et il est par exemple impossible de le parcourir simultanément de la tête à la queue et inversement. Elle ne sera donc pas implémentée pendant les TPs.
  • le conteneur offre plusieurs méthodes qui parcourent elles mêmes tout ou partie des éléments, et qui effectuent dessus un traitement spécifique. Pour gagner en généralité, ce traitement devrait être le plus général possible, en utilisant la généricité ou une technique analogue. Nous illustrerons cette approche par deux sortes de méthodes :
    • une fonction Look() capable de parcourir le conteneur à la recherche d'un élément particulier, ou d'insérer un nouvel élément,
    • une fonction ForEach() capable de parcourir le conteneur et d'appliquer à chacun de ses élément.
  • le conteneur offre la possibilité de créer des objets qui lui sont externes, mais qui permettent de le parcourir, et qui permettent chacun d'accéder à un élément du conteneur. Leur nombre n'est plus limité, et c'est l'utilisateur qui applique lui-même un traitement quel qu'il soit à l'élément accédé. Ces objets sont appelés des itérateurs déjà rencontrés pour les conteneurs standard.

  Les deux premières méthodes sont dites faire appel à des itérateurs internes et seront illustrées par différents exercices au cours de ce TP, la troisième utilise des itérateurs externes et sera étudiée au cours du prochain TP.

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

Sommaire

Conteneur "Liste"

exo_01

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

    Recopier les fichiers CLink2Gen.h, CLink2Gen.hxx, CContAbstr.h, CContAbstr.hxx, CStackAbstr.h, CFifoAbstr.h, CDequeAbstr.h, CConteneur_02.h, CConteneur_02.hxx, Makefile_05, soit de votre répertoire dirlstdouble, soit à partir des corrigés.

    Recopier les fichiers CCptIdent.h, CCptIdent.hxx, CCptIdent.cxx, soit de votre répertoire dirutilit, soit à partir des corrigés.

    Renommer CConteneur_02.h et CConteneur_02.hxx en CConteneur_01.h et CConteneur_01.hxx.

Classe CListAbstr

    Cette classe est analogue aux interfaces précédemment écrites, avec des méthodes particulières. Elle est la classe d'interface d'un conteneur "liste double" permettant de stocker des éléments de type générique T. Recopier CStackAbstr.h dans CListAbstr_01.h (il y aura plusieurs versions de cette classe). Remplacer l'identificateur Stack par List. Conserver la classe d'exceptions CExcList associée à la classe CListAbstr. Supprimer toutes les méthodes, et ajouter la méthode Look(), de profil :
 

virtual T * Look (const T & Elem, bool WithInsert = true) throw (CExcList) = 0;

• si le paramètre WithInsert est faux, la fonction se contente de rechercher l'élément Elem, et de renvoyer un pointeur nul si elle ne l'a pas trouvé, ou un pointeur vers l'élément de type T dont la valeur correspond à Elem,
• si le paramètre WithInsert est vrai, la fonction recherche l'élément Elem, l'ajoute n'importe où dans la liste si elle ne le trouve pas, et renvoie un pointeur vers l'élément T trouvé,
• si la liste est pleine (dépend de l'implémentation), la fonction Look() peut ne pas pouvoir insérer un nouvel élément. Elle doit alors lever une exception, dont le code d'erreur CstListePleine devra être ajouté dans le type énumératif de la classe CListAbstr.

1. l'utilisateur ne doit pas pouvoir modifier les chaînages des éléments de la liste. C'est pourquoi il doit recevoir de la fonction Look() un pointeur T * et non un pointeur CLinkT *.
2. puisque la liste ci-dessus ne suppose aucun ordre particulier des éléments, l'insertion doit être effectuée le plus facilement possible, c'est-à-dire en tête ou en queue.
3. une implémentation plus réaliste nécessiterait de pouvoir aussi supprimer des éléments.

    Les spécifications ci-dessus ajoutées à celles rencontrées précédemment imposent à la classe T d'être dérivable et de posséder :

• un constructeur par défaut (à cause des sentinelles) et un constructeur par copie (à cause de Depiler()),
• l'opérateur == pour effectuer la recherche. Cettre contrainte sur le type T semble soulever un problème de conception : l'ajout de l'interface CListAbstr à la classe CConteneur pour rendre cette dernière plus générale semble au contraire en réduire les possibilités puisqu'elle ne pourrait plus être instanciée comme pile, fifo et deque avec un type non pourvu de la relation d'identité. En fait, la fonction Look() est générique. A ce titre, il est très probable qu'elle ne soit instanciée que si elle est utilisée dans le programme. Dans ce cas, l'opérateur == est nécessaire. Mais si c'est une pile qui est utilisée, la fonction Look() ne sera pas instanciée et l'opérateur == ne sera pas utilisé.

  On peut aussi penser que c'est un défaut d'analyse de faire effectuer des traitements (une recherche par exemple) par un conteneur qui devrait se contenter de contenir ! Une alternative sera envisagée ultérieurement.

Classe CCptIdent

    Pour rendre possible l'instanciation de la classe CListe par la classe CCptIdent, celle-ci doit posséder les propriétés indiquées ci-dessus. Il est donc nécessaire de transformer le constructeur en constructeur par défaut.

Classe CConteneur

    Implémenter la fonction Look(). Ne disposant d'aucun moyen de vérifier que la liste est correctement remplie, ajouter provisoirement la fonction publique EditerListe(), qui parcourt toute la liste et affiche dans le flux qui lui est passé en paramètre tous les éléments qu'elle contient (sauf bien sûr les sentinelles), en utilisant l'opérateur << supposé surchargé pour la classe T. Cette solution est affreuse et ne sera pas conservée dans les versions ultérieures.

    Supprimer du fichier Makefile_01 tout ce qui est inutile, et ajouter les dépendances liées aux classes CCptIdent et CListAbstr.

    Dans le fichier exo_01.cxx, instancier la classe CConteneur avec la classe CCptIdent et, en utilisant la fonction Look() avec insertion, insérer des chaînes dans une liste en comptant leur nombre d'apparitions, puis afficher la liste. Tester enfin la fonction Look() sans insertion, sur des chaînes présentes et absentes de la liste.

    Compiler et tester.

Corrigés :      exo_01.cxx      -      CListAbstr_01.h      -      CConteneur_01.h      -      CConteneur_01.hxx      -      CCptIdent.h      -      CCptIdent.hxx      -      Makefile_01

Sommaire

Fonction ForEach() de base

exo_02

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

    Il est fréquent que l'utilisateur doive appliquer le même traitement à chaque élément d'une liste. Le conteneur doit donc proposer une méthode qui permet de parcourir tous les éléments et d'effectuer sur chacun le traitement qui lui est passé en paramètre.

    Recopier le fichier exo_01.cxx dans exo_02.cxx. Au début de l'espace anonyme, ajouter la fonction Editer() de profil :
 

void Editer (CCptIdent &);

qui affiche dans le flux standard de sortie l'objet CCptIdent qui lui est passé en paramètre.

    Recopier le fichier CListAbstr_01.h dans CListAbstr_02.h. Dans la partie publique de la classe CListAbstr, ajouter un type Fct1_t, qui est un pointeur vers une fonction à un paramètre, qui peut s'appliquer à un objet de la classe générique T et ne renvoie rien. Attention au type du paramètre : ignorant la nature du traitement appliqué, nous ne pouvons garantir que le paramètre est const). Ce type est celui de la fonction Editer() écrite ci-dessus. A son interface, ajouter la fonction virtuelle pure ForEach() ayant pour paramètre un pointeur vers la fonction à appliquer (de type Fct1_t).

    Recopier les fichiers CConteneur_01.h et CConteneur_01.hxx respectivement dans CConteneur_02.h et CConteneur_02.hxx. Implémenter la fonction ForEach(). Comme c'est elle qui sera utilisée dorénavant pour éditer la liste, la fonction Editer() peut être supprimée.

    Recopier le fichier Makefile_01 dans Makefile_02. Ajouter les dépendances liées aux fichiers CStackAbstr_02.h et CConteneur_02.*.

    Dans le fichier exo_02.cxx, remplacer les appels à la méthode Editer() de la classe CConteneur par des appels à la fonction ForEach().

    Compiler et tester.

Corrigés :      exo_02.cxx      -      CListAbstr_02.h      -      CConteneur_02.h      -      CConteneur_02.hxx      -      Makefile_02

Sommaire

Fonction ForEach() et technique du hook

exo_03

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

    La fonction ForEach() que nous avons écrite est très restrictive, car elle admet comme seul paramètre une fonction qui n'a elle-même comme paramètre qu'un objet de la classe T. On peut supposer que l'utilisateur soit conduit à effectuer sur chaque élément des traitements à deux paramètres ou plus. Il est évidemment impossible de définir autant de types de fonctions qu'il y a de nombres et de types de paramètres possibles. Le C++ offre la possibilité de définir des fonctions dont le profil comporte un nombre variable de paramètres, grâce au symbole ..., appelé "ellipse", comme le montre l'exemple ci-dessous :
 

template <typename T> void f (T & elem, ...);

qui précise que le premier paramètre doit être un objet de type T passé par référence, et qu'il peut y avoir d'autres paramètres de types indéfinis. Cette solution n'est pas applicable dans notre cas, car la fonction ForEach() ne pourrait appeler la fonction f() sans savoir quel(s) paramètre(s) lui passer.

    Une technique classique, appelée parfois dans la littérature un crochet ^[1] (hook), consiste à utiliser un seul paramètre formel supplémentaire, sous la forme d'un pointeur sans type void *. Cela permet de passer comme paramètre effectif un pointeur sur n'importe quel type, donnée ou résultat. En particulier il est possible de passer un pointeur sur une structure (class ou struct) comportant autant de données membres que le souhaite l'utilisateur et de n'importe quels types. Ainsi, en un seul paramètre, l'utilisateur peut faire passer autant d'informations qu'il le souhaite pour le traitement de chaque objet.

    Recopier le fichier CListAbstr_02.h dans CListAbstr_03.h. Y ajouter la déclaration du type Fct2_t pour que la fonction de traitement admette un second paramètre comme indiqué ci-dessus. A la classe CListAbstr, ajouter une surcharge de la fonction ForEach(), avec un second paramètre de type void *.

    Recopier les fichiers CConteneur_02.h et CConteneur_02.hxx dans les fichiers CConteneur_03.h et CConteneur_03.hxx. Ajouter l'implémentation de la nouvelle fonction ForEach() à deux paramètres.

    Recopier le fichier exo_02.cxx dans exo_03.cxx. La technique du crochet est tout d'abord illustrée en copiant la fonction Editer() écrite précédemment dans la fonction EditerDansFlux(), et en lui ajoutant un paramètre supplémentaire qui est un pointeur vers le flux de sortie à utiliser :
 

void EditerDansFlux (CCptIdent & Elem, ostream * os);

    Par défaut, tout pointeur est automatiquement transformé par le compilateur en void * si nécessaire. Le nouveau profil de la fonction EditerDansFlux() devrait donc être compatible avec le type Fct2_t. L'utilisation de la fonction ForEach() nécessite cependant de transtyper le paramètre effectif de ForEach() - le pointeur vers la fonction - dans le type Fct2_t de la classe CConteneur <CCptIdent>, ce qui peut être effectué au moyen d'une macro paramétrée :
 

#define CAST(objet) (reinterpret_cast <CConteneur <CCptIdent>::Fct2_t> (objet))

dont l'utilisation est la suivante :
 

UneListe->ForEach (CAST (EditerDansFlux), &cerr);

    Effectuer les modifications de la fonction Exo_03() pour continuer à pouvoir afficher le contenu de la liste avec la fonction Editer() écrite dans l'exercice précédent, et l'afficher aussi dans le flux cerr au moyen de EditerDansFlux().

    Après avoir recopié le fichier Makefile_02 dans Makefile_03 et l'avoir modifié pour ajouter les dépendances dues à CConteneur_03.h et CConteneur_03.hxx, compiler et tester.

    On désire cumuler les fréquences de tous les identificateurs stockés dans la liste et réaliser l'affichage suivant :
 

(numéro;  identificateur; fréquence; fréquence_cumulée)

soit, par exemple :
 

(1, Ch3, 2, 2); (2, Ch2, 3, 5); (3, Ch1, 3, 8); Nombre total d'identificateurs : 8

Dans l'espace anonyme du fichier exo_03.cxx, il faut ajouter :

• une structure SCumul qui comporte deux données membres :
  • l'entier m_Numero
  • l'entier m_Cumul
• une fonction globale Cumuler() qui ne renvoie rien, qui a pour paramètre un objet CCptIdent et un pointeur sur une structure SCumul, qui
  • incrémente le numéro,
  • effectue le cumul des fréquences,
  • effectue l'affichage comme indiqué plus haut.

    Dans la fonction Exo_03(), initialiser un objet SCumul, puis appeler la fonction ForEach() en initialisant correctement ses paramètres pour éditer les cumuls dans le format indiqué ci-dessus au moyen de la fonction Cumuler().

    Compiler et tester.

Corrigés :      exo_03.cxx      -      CListAbstr_03.h      -      CConteneur_03.h      -      CConteneur_03.hxx      -      Makefile_03

Sommaire

Premier functor

exo_04

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

    La technique du crochet utilisée ci-dessus est plus proche du C que du C++. En effet, elle utilise un pointeur void * comme paramètre formel de la fonction, ce qui prive le compilateur de tout contrôle possible. De plus, le transtypage systématique mais malheureusement nécessaire rend l'écriture pesante. Le C++ permet une solution d'une grande élégance, qui peut sembler complexe d'un premier abord, mais qui est intensivement utilisée dans la bibliothèque de C++ : les functors. Rappelons qu'un functor est un objet pour lequel l'opérateur fonction () a été surchargé ou, en d'autres termes, un objet qui peut :

• comme n'importe quel autre objet, être construit (par un constructeur), et stocker des données membres (initialisées par le constructeur ou des modifieurs,
• être appelé comme une fonction : avec une éventuelle liste de paramètres entre parenthèses. Dans ce cas, c'est le corps de la "fonction" operator () qui est exécuté.

    Dans les fichiers CFunctor_01.h et CFunctor_01.hxx, écrire la classe CFunctor ayant les caractéristiques suivantes :

• elle appartient à l'espace de noms nsWorking,
• chacune de ses instanciations est un functor, donc elle offre une surcharge de l'opérateur (). On désire que ce functor ait le même comportement que la fonction EditerDansFlux(). Pour cela, le constructeur du functor doit stocker dans une donnée membre le flux qui lui est passé en paramètre (avec une valeur par défaut), et dans lequel doit être effectuée l'injection des objets CCptIdent. En fait, la donnée membre ne peut être un flux, car on ne peut recopier un flux dans une donnée membre ! Cela pourrait être un pointeur de flux, comme :
   

  ostream * m_os;

  mais cette déclaration obligerait à écrire :
   

  (* m_os) << Elem;

  ce qui n'est pas élégant. On préfèrera donc que la donnée membre soit une référence à un flux, déclarée ainsi :
   

  ostream & m_os;

  qui permet l'écriture habituelle :
   

  m_os << Elem;

• Comme la fonction EditerDansFlux(), l'opérateur () doit admettre un CCptIdent comme paramètre donnée-résultat (passé par référence) :
   

  void operator () (CCptIdent & Element);

    Dans la fonction Exo_04() du fichier exo_04.cxx :

• déclarer deux functors de la classe CFunctor, en leur passant un flux de sortie en paramètre effectif, (cout et cerr),
• créer un CCptIdent, et le faire afficher par chaque functor.

    Copier Makefile_03 dans Makefile_04, et ajouter les dépendances dûes aux fichiers CFunctor_01.h et CFunctor_01.hxx.

    Compiler et tester.

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

Sommaire

functor générique

exo_05

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

    Nous avons montré dans l'exercice précédent qu'un functor peut s'utiliser en lieu et place d'une fonction. Le passage d'un functor en paramètre effectif est plus facile que celui d'un pointeur de fonction, qui nécessite souvent un transtypage. De plus, le corps de l'opérateur () du functor peut accéder non seulement à ses paramètres formels, mais aussi aux données membres de l'objet functor. Enfin, contrairement au passage d'une fonction en paramètre qui ne permet pas de récupérer des résultats, le passage d'un functor en paramètre donnée-résultat permet, en sortie, de récupérer les valeurs de ses données membres, qui peuvent être considérées comme des résultats de l'appel de la fonction.

    Dans le prochain exercice, le paramètre de la fonction ForEach() sera remplacé par un functor. Cependant, la classe CFunctor écrite précédemment est trop spécifique au type CCptIdent, et n'est donc pas directement utilisable dans un contexte générique tel que celui des conteneurs. Il faut donc commencer par la généraliser en créant un functor générique. De plus, ignorant totalement ce que devra effectuer l'opérateur (), cette fonction doit être virtuelle pure, la classe de functor générique est donc abstraite.

    Dans le fichier CFunctorGen.h, écrire la classe CFunctor1Param de l'espace de noms nsSdD, de paramètre de généricité Param1_t. Déclarer la méthode virtuelle pure operator() dont le paramètre donnée-résultat de type Param_t est passé par référence. Ne pas oublier le destructeur virtuel.

    Recopier les fichiers CFunctor_01.h et CFunctor_01_hxx dans CFunctor.h et CFunctor.hxx. Faire dériver la classe CFunctor de CFunctor1Param, et faire les modifications nécessaires.

    Recopier le fichier exo_04.cxx dans exo_05.cxx. En principe, la seule modification à effectuer est de remplacer l'inclusion du fichier CFunctor_01.h par CFunctor.h.

    Copier Makefile_04 dans Makefile_05, et ajouter les dépendances dûes aux fichiers CFunctorGen.h, CFunctor.h et CFunctor.hxx.

    Compiler et tester.

Corrigés :      exo_05.cxx      -      CFunctorGen.h      -      CFunctor.h      -      CFunctor.hxx      -      Makefile_05

Sommaire

Fonction ForEach() et functor générique

exo_06

• Liste des fichiers créés ou modifiés : exo_06.cxx, CListAbstr_04.h, CConteneur_04.h, CConteneur_04.hxx, Makefile_06

    Recopier les fichiers CListAbstr_03.h, CConteneur_03.h et CConteneur_03.hxx respectivement dans les fichiers CListAbstr_04.h, CConteneur_04.h et CConteneur_04.hxx. Il est maintenant possible d'ajouter à la classe CListAbstr une surcharge de la fonction ForEach() acceptant pour paramètre un functor générique de même pararmètre de généricité que la classe CListAbstr. Faire les modifications correspondantes dans les trois fichiers.

    Recopier le fichier exo_02.cxx dans exo_06.cxx. Supprimer la fonction Editer(), remplacer le fichier CConteneur_02.h par CConteneur_04.h, et inclure le fichier CFunctor.h. Déclarer un objet de la classe CFunctor, et le passer à la fonction ForEach() pour éditer la liste.

    Compiler et tester.

Corrigés :      exo_06.cxx      -      CListAbstr_04.h      -      CConteneur_04.h      -      CConteneur_04.hxx      -      Makefile_06

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