Remarques préliminaires :

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

Sommaire

Itérateur de liste

exo_01

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

    Nous avons indiqué plus haut que les itérateurs internes n'offrent pas suffisamment de possibilités pour parcourir les conteneurs (listes ou vecteurs). En revanche, les itérateurs, utilisés sur la classe générique standard vector dès les premiers TPs, sont largement mis en oeuvre dans la bibliothèque standard. L'objet de cet exercice est de doter le conteneur "liste double" créé dans le TP précédent d'un itérateur simple, pouvant progresser dans les deux sens dans la liste. Nous ne distinguerons pas les cas des const_(reverse)_iterators qui ne présentent aucun intérèt pédagogique supplémentaire, car très simples à ajouter. Comme d'habitude, le but de l'exercice est plus de montrer le principe d'un itérateur que de développer une classe totalement opérationnelle.

Classe CIterAbstr

Indépendamment de l'implémentation du conteneur séquentiel (essentiellement la liste pour nous), et donc de l'itérateur qui le parcourt, on peut définir les caractéristiques que doit avoir ce dernier :

• permettre d'accéder à un élément du conteneur,
• permettre de passer à l'élément précédent ou au suivant,
• pouvoir être initialisé, (initialisation de début de boucle de parcours, par exemple),
• pouvoir être comparé à un autre itérateur (test de fin de boucle).

    Dans le fichier CIterAbstr_01.h, écrire la classe d'exception CExcIter dans l'espace de noms nsSdD, qui sera associée aux erreurs de manipulation d'itérateurs, selon le modèle habituel (voir par exemple la classe CStackAbstr_01.h). Dans ce même fichier, ajouter la classe générique abstraite CIterAbstr, toujours dans l'espace de noms nsSdD, représentant une interface d'itérateur, et ayant les méthodes virtuelles pures suivantes :

• les opérateurs de pré-incrémentation ++ et de pré-décrémentation -- (on pourrait aussi désirer les post-incrémentation et post-décrémentation, mais nous expliquerons ultérieurement pourquoi ce n'est pas possible avec la structure choisie),
• l'opérateur d'égalité ==,
• les opérateurs d'accès à l'élément pointé * et -> ^[2]. C'est l'existence de ces deux fonctions qui nécessitent que la classe soit générique, le paramètre de généricité étant le type de l'objet pointé.

    Deux sortes d'erreurs sont prévisibles, indépendamment des implémentations du conteneur et de l'itérateur associé :

• comme dans la bibliothèque standard, un itérateur peut être déclaré sans pour cela être attaché à un conteneur particulier. La plupart des opérations sur les itérateurs lui sont interdites, comme le montre l'exemple suivant :
   

  vector <int> VInt; ... vector <int>::iterator It; cout << *It << end;       // opération interdite It = VInt.begin(); cout << *It << end;       // opération autorisée

• même si l'itérateur est valide, certaines opérations sont interdites, comme la tentative de passage au-delà de end(), en-deça de begin(), ou l'accès à l'élément si l'itérateur vaut end().

    A la classe CExcIter ajouter les constantes CstIterInvalide et CstOutOfRange correspondant à ces deux types d'erreurs.

Classe CListAbstr

La classe CListAbstr écrite dans le TP précédent doit être enrichie. En effet, elle doit posséder deux méthodes permettant de positionner un itérateur en début de liste et de vérifier s'il a atteint la fin de la liste.

    Dans le fichier CListAbstr_01.h, recopier votre fichier dirliste/CListAbtr_04.h ou le corrigé. Supprimer les deux déclarations de type Fct1_t et Fct2_t, ainsi que les trois fonctions ForEach() (les itérateurs les rendent inutiles) et les fichiers inclus associés. Ajouter les deux membres virtuelles pures de profils suivants (qui seront justifiés ultérieurement) :
 

virtual const CIterAbstr <T> & begin (void) = 0; virtual const CIterAbstr <T> & end   (void) = 0;

Classe CIterGen

Les classes d'itérateurs et de conteneurs sont liées entre elles :

• un itérateur doit être liée à un conteneur, puisque certaines de ses méthodes utilisent les fonctions membres begin() et end() du conteneur pour valider leurs actions. La classe itérateur doit donc contenir un pointeur m_Conteneur vers le conteneur associé ;
• la classe d'itérateurs doit être générique (de type U par exemple), puisque la méthode * renvoie un objet de type générique U, et ce paramètre de généricité doit être le même que celui du conteneur auquel l'itérateur est lié. La donnée membre ci-dessus doit dont être déclarée :
   

  CConteneur <U> * m_Conteneur;

• un itérateur initialisé doit aussi pointer sur un élément de la liste chaînée du conteneur. Il doit donc posséder une donnée membre m_Courant, déclarée ainsi :
   

  CLink2Gen <U> * m_Courant;

  Pour plus de commodités, le type anonyme CLink2Gen <U> peut évidemment être nommé au moyen de l'instruction typedef ;

• les deux données membres de l'itérateur renvoyé par les méthodes begin() ou end() du conteneur doivent donc être initialisés par le conteneur. Ceci ne peut être fait que par des fonctions membres de l'itérateur (constructeur ou modifieurs). Or ces opérations doivent être interdites à l'utilisateur de l'itérateur, qui ne doit pas pouvoir modifier la donnée membre m_Courant par exemple que par les opérateurs ++ ou --. Le conteneur doit donc avoir des privilèges étendus par rapport à l'utilisateur normal, qui ne peuvent être obtenus qu'en déclarant la classe conteneur amie (friend) de la classe itérateur ;

    Afin d'alléger les fichiers, le conteneur n'implémentera plus que l'interface CListAbstr. Les interfaces de pile, de fifo et de deque sont donc supprimés, et le fichier Makefile simplifié. Afin de gagner du temps, recopier dans les fichier CConteneur_01.h, CConteneur_01.hxx et Makefile_01, les fichiers CConteneur_01.h.init, CConteneur_01.hxx.init et Makefile_01.init du répertoire : ~mathieu/PARTAGE/src/tp/tpC++/tpliste2/dirliste2.

    Dans le fichier CConteneur_01.h, entre les classes CExcCont et CConteneur, ajouter les déclarations incomplètes des deux classes CIterGen et CConteneur :
 

template <class U> class CIterGen; template <class T> class CConteneur;

puis la déclaration complète de la classe générique CIterGen dérivée de la classe abstraite d'interface CIterAbstr :

• déclarer amie la classe CConteneur instanciée par le même type,
• nommer le type CLink2Gen instancié par le type du paramètre générique (on peut à nouveau utiliser l'identificateur CLinkT, qui sera distinct de celui de la classe CConteneur déjà déclaré),
• ajouter les données membres, privées, m_Conteneur et m_Courant conformément à ce qui a été indiqué plus haut,
• ajouter les méthodes privées suivantes :
   

  CIterGen (CConteneur <U> * const Conteneur, CLinkT * const Ptr); void ValiderConteneur (void) const throw (CExcIter); void ValiderIter (const CIterGen & Iter) const throw (CExcIter);

  • Le constructeur privé sera utilisé par la classe conteneur dans les focntions begin() et end().
  • La fonction ValiderConteneur() sera appelée pour vérifier que l'itérateur est bien associé avec un conteneur à chaque opération qui le nécessitera. Dans le cas contraire, l'exception CExcIter avec le code d'erreur CstIterInvalide sera levée.
  • b La fonction ValiderIter() sera appelée chaque fois qu'il faudra vérifier que l'opération tentée sur un itérateur est autorisée. Cette opération sera interdite si l'itérateur est égal à l'itérateur passé en paramètre (par exemple dans la préincrémentation si l'itérateur vaut end()). Dans ce cas, l'exception CExcIter avec le code d'erreur CstOutOfRange sera levée.
• dans la partie publique, ajouter :
  • un constructeur par défaut, permettant à l'utilisateur de déclarer un itérateur sans le lier à un conteneur,
  • un destructeur virtuel (la classe CIterGen dérive d'une classe abstraite),
  • la surcharge de toutes les fonctions abstraites héritées de la classe CIterAbstr.

Remarques

1. Malgré la présence de pointeurs comme données membres, les surcharges du constructeur par copie et de l'affectation ne sont pas nécessaires. En effet, la duplication d'un itérateur ne doit recopier que les pointeurs et non les objets pointés (la liste !).
2. La surcharge de certaines fonctions n'est pas évidente : par exemple, l'opérateur == doit avoir la même signature que la fonction qu'elle surcharge, soit :
    

   virtual bool operator == (const CIterAbstr <U> & Iter) const throw (CExcIter);

   et non
    

   virtual bool operator == (const CIterGen <U> & Iter) const throw (CExcIter);

   comme on aurait pu le penser. Dans l'implémentation de cette fonction, il y aura donc un conflit entre le type du premier opérande (celui sur lequel sera appelé l'opérateur), de type CIterGen <U>, et celui du paramètre, de type CIterAbstr <U>. Un transtypage sera donc nécessaire.

Classe CConteneur

Au début de la classe, ajouter en public la définition du type CIterator, qui est une instanciation du type CIterGen avec le paramètre de généricité du conteneur. Pour déclarer un itérateur dans son programme, l'utilisateur utilisera ce type :
 

typedef CConteneur CListIdent; CListIdent * UneListe = new CListIdent; for (CListIdent::CIterator Iter = UneListe->begin ();      Iter != UneListe->end (); ++Iter)      // ...

    Puisque toute liste doit fournir deux itérateurs, de la classe CIterator, pointant l'un sur le premier élément de la liste (le suivant de la tête), et l'autre au-delà du dernier élément (sur la sentinelle de queue ^[1]), nous avons choisi d'en faire deux données membres du conteneur, avec pour avantage de ne pas avoir à appeler un constructeur d'itérateur chaque fois que l'une des fonctions begin() ou end() est appelée. Il est donc inutile que ces fonctions en retournent une copie, il suffit qu'elles en retournent la référence, garantissant cependant qu'ils ne peuvent être modifiés par l'utilisateur au moyen du qualifieur const.

    A la classe CConteneur, ajouter les données membres privées m_begin et m_end de type CIterator. La première pointe sur le premier élément de la liste (celui qui suit m_Tete) et évolue donc au cours du temps. Elle sera mise à jour à chaque appel de la fonction begin(). En revanche, la seconde est constante et sera initialisée une fois pour toutes dans le constructeur.

    Dans le fichier exo_01.cxx, tester les différentes possibilités de parcours d'une liste.

    Modifier le fichier Makefile_01 pour prendre en compte la classe CIterAbstr.

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

Sommaire

Fonction ForEach() générique

exo_02

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

    La bibliothèque C++ a très clairement séparé :

• les classes conteneurs, dont le seul rôle est ... de contenir des objets, sans préjuger des traitements qui leur seront appliqués, et
• les algorithmes génériques, dont le rôle est d'implémenter des traitements sur des objets, quelle que soit la nature du conteneur qui contient ces objets.

Afin de pouvoir appliquer les seconds (les algorithmes) aux premiers (les conteneurs), les concepteurs ont inventé les itérateurs externes, souvent appelés dans la littérature "la glu" car ils font le lien entre les deux. Puisque nous disposons maintenant d'itérateurs, il reste à illustrer la technique de fabrication des algorithmes. Nous l'illustrerons sur la fonction bien connue ForEach().

    Puisqu'un conteneur est accessible à partir d'un itérateur instancié, la fonction ForEach() n'a pas besoin de savoir sur quel conteneur elle est appliquée. Il suffit de lui passer deux itérateurs, qui définissent une "tranche" (un intervalle semi-ouvert) valide : les deux itérateurs doivent désigner le même conteneur. On pourrait s'en assurer dans la fonction, mais, pour simplifier, on supposera que c'est de la responsabilité de l'utilisateur (mauvaise supposition ...). Comme précédemment, le traitement à appliquer sera passé en troisième paramètre, sous la forme maintenant bien connue, et maîtrisée, d'un functor. Dans le cas général, les itérateurs peuvent être de type quelconque, pourvu qu'ils soient de même type : [const_][reverse_]iterator sur des listes ou des vectors de n'importe quoi. Le type des deux premiers paramètres est donc le type de généricité de la fonction ForEach().

    La fonction ForEach() a un autre paramètre de généricité, implicite : le troisième paramètre est un functor générique instancié exactement par le même type que celui qui a servi à intancier l'itérateur et le conteneur qui lui est associé. Il ne faut pas que l'utilisateur ait à indiquer ce second paramètre de généricité pour trois raisons :

• il ne faut pas lui faire confiance,
• il ne faut jamais demander une information qu'on peut obtenir par soi-même,
• de toutes façons, une fonction n'est jamais instanciée explicitement en C++, mais seulement par le compilateur lorsqu'il en a besoin.

    Il est possible et simple de récupérer le type d'un paramètre générique d'une classe, comme le montre l'exemple suivant :
 

template <typename T> class CX { // ... public : typedef T value_type; // ... }; // CX typedef CX <char> NouveauType; // ... // Supposons qu'à l'instruction suivante, la définition de NouveauType ne soit plus visible : // NouveauType::value_type X; // X est de type char

    Recopier le fichiers CIterAbstr_01.h dans CIterAbstr_02.h. Dans la partie publique de la classe, ajouter la déclaration du type value_type (c'est un identificateur standard dans la bibliothèque C++) qui représente le type générique.

    Dans les fichiers Algo.h et Algo.hxx, déclarer et définir dans l'espace de nons nsSdD la fonction ForEach() conformément aux indications ci-dessus.

    Recopier le fichier dirliste/exo_06.cxx dans exo_02.cxx. Le modifier pour qu'il utilise la nouvelle fonction ForEach().

    Recopier le fichier Makefile_01 dans Makefile_02 et ajouter les dépendances dues aux fichiers Algo.*.

    Compiler et tester.

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

Sommaire

Allocation de mémoire par granule

exo_03

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

Sommaire

[2] La surcharge de l'opérateur -> a été effectuée dans l'exo_05 du TP 10 : "Pointeurs intelligents" : voir les fichiers CStack.h et CStack.hxx

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