Penser en C++

Imaginez que vous vouliez créer une pile (stack, ndt), comme nous l'avons tout au long du livre. Cette classe stack contiendra des int, pour faire simple :

//: C16:IntStack.cpp
// Pile d'entiers simple 
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;
 
class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
};
 
int main() {
  IntStack is;
  // Ajoute des nombres des Fibonacci, par curiosité :
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Les dépile & les affiche :
  for(int k = 0; k < 20; k++)
    cout << is.pop() << endl;
} ///:~

La classs IntStack est un exemple trivial d'une pile refoulée. Par souci de simplicité, elle a été créée ici avec une taille constante, mais vous pouvez aussi la modifier pour s'accroître automatiquement en allouant de la mémoire sur le tas, comme dans la classe Stack que l'on a examinée tout au long de ce livre.

main( ) ajoute des entiers à la pile, puis les dépile. Pour rendre l'exemple plus intéressant, les entiers sont créés à l'aide de la fonction fibonacci( ), qui génère les traditionnels nombres de la reproduction des lapins (ndt : la suite de Fibonacci trouve son origine dans l'étude de la vitesse de reproduction des lapins dans un milieu idéal par Fibonacci (XIIIe siècle)). Voici le fichier d'en-tête qui déclare la fonction :

//: C16:fibonacci.h
// Générateur de nombres de Fibonacci
int fibonacci(int n); ///:~

Voici l'implémentation :

//: C16:fibonacci.cpp {O}
#include "../require.h"
 
int fibonacci(int n) {
  const int sz = 100;
  require(n < sz);
  static int f[sz]; // Initialisé à zéro
  f[0] = f[1] = 1;
  // recherche d'éléments non remplis du tableau :
  int i;
  for(i = 0; i < sz; i++)
    if(f[i] == 0) break;
  while(i <= n) {
    f[i] = f[i-1] + f[i-2];
    i++;
  }
  return f[n];
} ///:~

C'est une implémentation relativement efficace, parce qu'elle ne génère jamais les nombres plus d'une fois. Elle utilise un tableau static de int, et repose sur le fait que le compilateur initialisera un tableau de static à zéro. La première boucle for déplace l'index i au niveau du premier élément à zéro du tableau, puis une boucle while ajoute des nombres de Fibonacci au tableau jusqu'à ce que l'élément voulu soit atteint. Mais remarquez que si les nombres de Fibonacci jusqu'à l'élément n sont déjà initialisés, la boucle while est entièrement évitée.

XVII-A-1. Le besoin de conteneurs▲

Un problème apparaît, à présent. Vous disposez d'un IntStack, qui contient des entiers. Mais vous voulez une pile qui contient des formes ou des avions ou des plantes ou autres choses. Réinventer votre code source à chaque fois ne semble pas être une approche très intelligente avec un langage qui promeut la réutilisabilité. Il doit exister une meilleure technique.

Il y a trois techniques pour la réutilisation du code source dans cette situation : la manière du C, présentée ici pour comparer ; l'approche de Smalltalk, qui a significativement influencé le C++ ; et l'approche du C++ : les templates.

La solution du C. Bien sûr, vous essayez de vous affranchir de l'approche du C parce qu'elle est sale, source d'erreurs et complètement inélégante. Dans cette approche, vous copiez le code source pour un Stack et faites les modifications à la main, introduisant de cette façon de nouvelles erreurs. Ce n'est certainement pas une technique très productive.

La solution Smalltalk. Le Smalltalk (et Java, qui suit son exemple) a adopté une approche simple et directe : vous voulez réutiliser le code, utilisez donc l'héritage. Pour implémenter cela, chaque classe de conteneur contient des items de la classe de base générique Object(similaire à l'exemple de la fin du Chapite 15). Mais puisque la bibliothèque en Smalltalk est d'une importance si fondamentale, vous ne créez jamais une classe à partir de rien. Au lieu de cela, vous devez toujours la faire hériter d'une classe existante. Vous trouvez une classe aussi proche que possible de celle que vous voulez, vous en dérivez, et faites quelques changements. De toute évidence, c'est un progrès parce que cela minimise vos efforts (et explique pourquoi vous devez passer beaucoup de temps à apprendre la bibliothèque de classes avant de devenir un programmeur efficace en Smalltalk).

Mais cela signifie également que toutes les classes en Smalltalk finissent par appartenir à un arbre d'héritage unique. Vous devez hériter d'une branche de cet arbre quand vous créez une classe. L'essentiel de l'arbre est déjà là (c'est la bibliothèque de classes de Smalltalk), et à la racine de l'arbre se trouve une classe appelée Object–la même classe que contient chaque conteneur de Smalltalk.

C'est une belle astuce parce que cela signifie que toute classe dans la hiérarchie de classe de Smalltalk (et de Java (59)) est dérivée d' Object, si bien que toute classe peut être contenue dans chaque conteneur (y compris le conteneur lui-même). Ce type de hiérarchie à arbre unique basée sur un type générique fondamental (souvent appelé Object, ce qui est aussi le cas en Java) est dénommée “hiérarchie basée sur une classe object”. Vous avez peut-être entendu ce terme et imaginé que c'était un nouveau concept fondamental en POO, comme le polymorphisme. Cela fait simplement référence à une hiérarchie de classe avec Object(ou un nom similaire) à sa racine et des classes conteneurs qui contiennent Object.

Comme il y a beaucoup plus d'histoire et d'expérience derrière la bibliothèque de classes de Smalltalk que celle du C++, et puisque les compilateurs originaux du C++ n'avaient aucune bibliothèque de classes de conteneurs, cela semblait une bonne idée de dupliquer la bibliothèque de Smalltalk en C++. Ceci a été fait à titre expérimental avec une ancienne implémentation du C++ (60), et comme cela représentait une quantité de code importante, beaucoup de gens ont commencé à l'utiliser. En essayant d'utiliser les classes de conteneurs, ils ont découvert un problème.

Le problème était qu'en Smalltalk (et dans la plupart des autres langages orientés objet que je connais), toutes les classes sont automatiquement dérivées d'une hiérarchie unique, mais ce n'est pas vrai en C++. Vous pourriez avoir votre sympathique hiérarchie basée sur une classe object, avec ses classes de conteneurs, mais vous pouvez alors acheter un ensemble de classes de formes ou d'avions d'un autre vendeur qui n'utilise pas cette hiérarchie. (Pour une raison, utiliser cette hiérarchie coûte du temps système, ce que les programmeurs C évitent). Comment insérez-vous un arbre de classe différent dans la classe de conteneurs de votre hiérarchie basée sur une classe object ? Voici à quoi ressemble le problème :

Parce que le C++ supporte plusieurs hiérarchies indépendantes, la hiérarchie basée sur une classe object de Smalltalk ne fonctionne pas si bien.

La solution parut évidente. Si vous pouvez avoir beaucoup de hiérarchies d'héritage, vous devriez alors pouvoir hériter de plus d'une classe : l'héritage multiple résoudra le problème. Vous procédez alors comme suit (un exemple similaire a été donné à la fin du Chapitre 15) :

À présent OShape a les caractéristiques et le comportement de Shape, mais comme il dérive aussi de Object il peut être placé dans un Container. L'héritage supplémentaire dans OCircle, OSquare, etc. est nécessaire afin que ces classes puissent être transtypées en OShape et conserver ainsi le comportement correct. Vous vous rendez compte que les choses deviennent rapidement embrouillées.

Les vendeurs de compilateurs ont inventé et inclus leurs propres hiérarchies de classes de conteneurs basées sur une classe object, la plupart desquelles ont depuis été remplacées par des versions templates. Vous pouvez souligner que l'héritage multiple est nécessaire pour résoudre des problèmes de programmation générale, mais vous verrez dans le volume 2 de ce livre qu'il vaut mieux éviter sa complexité sauf dans certains cas particuliers.

XVII-B-1. La solution template▲

Bien qu'une hiérarchie basée sur une classe object avec héritage multiple soit conceptuellement claire, son utilisation s'avère douloureuse. Dans son livre original (61)Stroustrup a démontré ce qu'il considérait comme une alternative préférable à la hiérarchie basée sur une classe object. Les classes de conteneurs étaient créées sous forme de grandes macros du préprocesseur avec des arguments qui pouvaient être substitués par le type que vous désirez. Quand vous vouliez créer un conteneur pour stocker un type particulier, vous faisiez une paire d'appels de macros.

Malheureusement, cette approche a été embrouillée par toute la littérature et l'expérience de programmation existantes en Smalltalk, et elle était un peu difficile à manier. En gros, personne ne la comprenait.

Entre temps, Stroustrup et l'équipe C++ des Bell Labs avaient modifié leur approche macro originale, en la simplifiant et en la déplaçant du domaine du préprocesseur vers celui du compilateur. Ce nouvel outil de substitution de code est appelé un template(62), et cela représente une façon complètement différente de réutiliser le code. Au lieu de réutiliser le code objet, comme avec l'héritage et la composition, un template réutilise le code source. Le conteneur ne stocke plus une classe générique de base appelée Object, mais stocke à la place un paramètre non spécifié. Quand vous utilisez un template, le paramètre est substitué par le compilateur, de manière très semblable à l'ancienne approche par les macros, mais de façon plus propre et plus facile à utiliser.

Maintenant, au lieu de devoir s'inquiéter d'héritage ou de composition quand vous voulez utiliser une classe de conteneur, vous prenez la version template du conteneur et fabriquez une version spécifique pour votre problème particulier, comme ceci :

Le compilateur fait le travail pour vous, et vous vous retrouvez avec exactement le conteneur dont vous avez besoin pour faire le travail, plutôt qu'une hiérarchie d'héritage indémêlable. En C++, le template implémente le concept de type paramétré. Un autre bénéfice de l'approche template est que le programmeur novice qui n'est pas nécessairement familier ou à l'aise avec l'héritage peut tout de même utiliser les classes de conteneurs immédiatement (comme nous l'avons fait avec vector tout au long du livre).

Le mot-clé template dit au compilateur que la définition de classe qui suit manipulera un ou plusieurs types non spécifiés. Au moment où le code réel de la classe est généré à partir du template, ces types doivent être spécifiés afin que le compilateur puisse les substituer.

Pour démontrer la syntaxe, voici un petit exemple qui produit un tableau dont les bornes sont vérifiées :

//: C16:Array.cpp
#include "../require.h"
#include <iostream>
using namespace std;
 
template<class T>
class Array {
  enum { size = 100 };
  T A[size];
public:
  T& operator[](int index) {
    require(index >= 0 && index < size,
      "Index out of range");
    return A[index];
  }
};
 
int main() {
  Array<int> ia;
  Array<float> fa;
  for(int i = 0; i < 20; i++) {
    ia[i] = i * i;
    fa[i] = float(i) * 1.414;
  }
  for(int j = 0; j < 20; j++)
    cout << j << ": " << ia[j]
         << ", " << fa[j] << endl;
} ///:~

Vous pouvez voir que cela ressemble à une classe normale, sauf en ce qui concerne la ligne

template<class T&gt;

qui dit que T est le paramètre de substitution, et qu'il représente un nom de type. Vous voyez également que T est utilisé dans la classe partout où vous verriez normalement le type spécifique stocké par le conteneur.

Dans Array, les éléments sont insérés et extraits avec la même fonction : l'opérateur surchargé operator [ ]. Il renvoie une référence, afin qu'il puisse être utilisé des deux côtés d'un signe égal (c'est-à-dire à la fois comme lvalue et comme rvalue). Notez que si l'index est hors limite, la fonction require( ) est utilisée pour afficher un message. Comme operator[] est inline, vous pourriez utiliser cette approche pour garantir qu'aucune violation des limites du tableau ne se produit, puis retirer require( ) pour le code livré.

Dans main( ), vous pouvez voir comme il est facile de créer des Array qui contiennent différents types. Quand vous dites

Array<int&gt; ia;
Array<float&gt; fa;

le compilateur développe le template Array(c'est appelé instanciation) deux fois, pour créer deux nouvelles classes générées, que vous pouvez considérer comme Array_int et Array_float. (Différents compilateurs peuvent décorer les noms de façons différentes.) Ce sont des classes exactement comme celles que vous auriez produites si vous aviez réalisé la substitution à la main, sauf que le compilateur les crée pour vous quand vous définissez les objets ia et fa. Notez également les définitions de classes dupliquées sont soit évitées par le compilateur, soit fusionnées par l'éditeur de liens.

XVII-C-1. Définitions de fonctions non inline▲

//: C16:Array2.cpp
// Définition de template non-inline 
#include "../require.h"
 
template<class T>
class Array {
  enum { size = 100 };
  T A[size];
public:
  T& operator[](int index);
};
 
template<class T>
T& Array<T>::operator[](int index) {
  require(index >= 0 && index < size,
    "Index out of range");
  return A[index];
}
 
int main() {
  Array<float> fa;
  fa[0] = 1.414;
} ///:~

XVII-C-2. IntStack comme template▲

//: C16:StackTemplate.h
// Template stack simple 
#ifndef STACKTEMPLATE_H
#define STACKTEMPLATE_H
#include "../require.h"
 
template<class T>
class StackTemplate {
  enum { ssize = 100 };
  T stack[ssize];
  int top;
public:
  StackTemplate() : top(0) {}
  void push(const T& i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  T pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  int size() { return top; }
};
#endif // STACKTEMPLATE_H ///:~

//: C16:StackTemplateTest.cpp
// Teste le template stack simple
//{L} fibonacci
#include "fibonacci.h"
#include "StackTemplate.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
 
int main() {
  StackTemplate<int> is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  for(int k = 0; k < 20; k++)
    cout << is.pop() << endl;
  ifstream in("StackTemplateTest.cpp");
  assure(in, "StackTemplateTest.cpp");
  string line;
  StackTemplate<string> strings;
  while(getline(in, line))
    strings.push(line);
  while(strings.size() > 0)
    cout << strings.pop() << endl;
} ///:~

XVII-C-3. Constantes dans les templates▲

//: C16:Array3.cpp
// Types prédéfinis comme arguments de template
#include "../require.h"
#include <iostream>
using namespace std;
 
template<class T, int size = 100>
class Array {
  T array[size];
public:
  T& operator[](int index) {
    require(index >= 0 && index < size,
      "Index out of range");
    return array[index];
  }
  int length() const { return size; }
};
 
class Number {
  float f;
public:
  Number(float ff = 0.0f) : f(ff) {}
  Number& operator=(const Number& n) {
    f = n.f;
    return *this;
  }
  operator float() const { return f; }
  friend ostream&
    operator<<(ostream& os, const Number& x) {
      return os << x.f;
  }
};
 
template<class T, int size = 20>
class Holder {
  Array<T, size>* np;
public:
  Holder() : np(0) {}
  T& operator[](int i) {
    require(0 <= i && i < size);
    if(!np) np = new Array<T, size>;
    return np->operator[](i);
  }
  int length() const { return size; }
  ~Holder() { delete np; }
};
 
int main() {
  Holder<Number> h;
  for(int i = 0; i < 20; i++)
    h[i] = i;
  for(int j = 0; j < 20; j++)
    cout << h[j] << endl;
} ///:~

Les problèmes récurrents de “propriété” avec les classes de conteneurs Stash et Stack qui ont été revisitées tout au long de ce livre viennent du fait que ces conteneurs n'ont pas été capables de savoir exactement quels types ils contiennent. Le plus proche qu'ils ont trouvé est le conteneur Stack“conteneur d' Object”qui a été vu à la fin du Chapitre 15 dans OStackTest.cpp.

Si le programmeur client ne supprime pas explicitement les pointeurs sur objets qui sont contenus dans le conteneur, alors le conteneur devrait être capable d'effacer correctement ces pointeurs. Il faut le dire, le conteneur “s'approprie” tous les objets qui n'ont pas été supprimés, et est ainsi chargé de leur effacement. Le hic est que le nettoyage nécessite de connaitre le type de l'objet, et que la création d'une classe de conteneur générique nécessite de ne pas connaitre le type de l'objet. Avec les templates, cependant, nous pouvons écrire du code qui ne connait pas le type de l'objet, et modéliser facilement une nouvelle version du conteneur pour chaque type que nous voulons contenir. Les conteneurs modélisés individuels connaissent le type des objets qu'ils contiennent et peuvent ainsi appeler le destructeur correct (en supposant, dans le cas typique où le polymorphisme est mis en jeu, qu'un destructeur virtuel a été fourni).

Pour Stack cela se révèle être assez simple puisque toutes les fonctions membres peuvent être raisonnablement « inlined »:

//: C16:TStack.h
// Stack comme template
#ifndef TSTACK_H
#define TSTACK_H
 
template<class T>
class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt): 
      data(dat), next(nxt) {}
  }* head;
public:
  Stack() : head(0) {}
  ~Stack(){ 
    while(head)
      delete pop();
  }
  void push(T* dat) {
    head = new Link(dat, head);
  }
  T* peek() const {
    return head ? head->data : 0; 
  }
  T* pop(){
    if(head == 0) return 0;
    T* result = head->data;
    Link* oldHead = head;
    head = head->next;
    delete oldHead;
    return result;
  }
};
#endif // TSTACK_H ///:~

Si vous comparez cela à l'exemple OStack.h à la fin du Chapitre 15, vous verrez que Stack est virtuellement identique, excepté le fait que Object a été remplacé par T. Le programme de test est aussi presque identique, excepté le fait que la nécessité pour le multihéritage, de string et de Object(et même la nécessité pour Object lui-même) a été éliminée. Maintenant il n'y a pas de classe MyString pour annoncer sa destruction, ainsi une nouvelle petite classe est ajoutée pour montrer qu'un conteneur Stack efface ses objets:

//: C16:TStackTest.cpp
//{T} TStackTest.cpp
#include "TStack.h"
#include "../require.h"
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
 
class X {
public:
  virtual ~X() { cout << "~X " << endl; }
};
 
int main(int argc, char* argv[]) {
  requireArgs(argc, 1); // File name is argument
  ifstream in(argv[1]);
  assure(in, argv[1]);
  Stack<string> textlines;
  string line;
  // Lit le fichier et stocke les lignes dans Stack:
  while(getline(in, line))
    textlines.push(new string(line));
  // Saute quelques lignes de Stack:
  string* s;
  for(int i = 0; i < 10; i++) {
    if((s = (string*)textlines.pop())==0) break;
    cout << *s << endl;
    delete s; 
  } // Le destructeur efface les autres chaines de caractères.
  // Montre que la destruction correcte a lieu:
  Stack<X> xx;
  for(int j = 0; j < 10; j++)
    xx.push(new X);
} ///:~

Le destructeur pour X est virtuel, non pas parce que cela est nécessaire ici, mais parce que xx pourrait être utilisé plus tard pour contenir des objets derivés de X.

Notez comme il est facile de créer différentes sortes de Stacks pour strings et pour X. Grâce au template, vous obtenez le meilleur des deux mondes: la facilité d'utilisation de la classe Stack avec un nettoyage approprié.

XVII-D-1. Pointeur Stash modélisé▲

//: C16:TPStash.h
#ifndef TPSTASH_H
#define TPSTASH_H
 
template<class T, int incr = 10>
class PStash {
  int quantity; // Nombre d'espaces de stockage
  int next; // Prochain espace vide
  T** storage;
  void inflate(int increase = incr);
public:
  PStash() : quantity(0), next(0), storage(0) {}
  ~PStash();
  int add(T* element);
  T* operator[](int index) const; // Fetch
  // Efface la référence de ce PStash:
  T* remove(int index);
  // Nombre d'éléments dans Stash:
  int count() const { return next; }
};
 
template<class T, int incr>
int PStash<T, incr>::add(T* element) {
  if(next >= quantity)
    inflate(incr);
  storage[next++] = element;
  return(next - 1); // Index number
}
 
// Propriété des pointeurs restants:
template<class T, int incr>
PStash<T, incr>::~PStash() {
  for(int i = 0; i < next; i++) {
    delete storage[i]; // Null pointers OK
    storage[i] = 0; // Just to be safe
  }
  delete []storage;
}
 
template<class T, int incr>
T* PStash<T, incr>::operator[](int index) const {
  require(index >= 0,
    "PStash::operator[] index negative");
  if(index >= next)
    return 0; // To indicate the end
  require(storage[index] != 0, 
    "PStash::operator[] returned null pointer");
  // Produit un pointeur pour l'élément désiré:
  return storage[index];
}
 
template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
  // operator[] exécute des contrôles de validité:
  T* v = operator[](index);
  // "Supprime" le pointeur:
  if(v != 0) storage[index] = 0;
  return v;
}
 
template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
  const int psz = sizeof(T*);
  T** st = new T*[quantity + increase];
  memset(st, 0, (quantity + increase) * psz);
  memcpy(st, storage, quantity * psz);
  quantity += increase;
  delete []storage; // Ancien stockage
  storage = st; // Pointe vers la nouvelle mémoire
}
#endif // TPSTASH_H ///:~

//: C16:AutoCounter.h
#ifndef AUTOCOUNTER_H
#define AUTOCOUNTER_H
#include "../require.h"
#include <iostream>
#include <set> // conteneur de la Bibliothèque Standard C++
#include <string>
 
class AutoCounter {
  static int count;
  int id;
  class CleanupCheck {
    std::set<AutoCounter*> trace;
  public:
    void add(AutoCounter* ap) {
      trace.insert(ap);
    }
    void remove(AutoCounter* ap) {
      require(trace.erase(ap) == 1,
        "Tentative de double suppression de AutoCounter");
    }
    ~CleanupCheck() {
      std::cout << "~CleanupCheck()"<< std::endl;
      require(trace.size() == 0,
       "Tous les objets AutoCounter ne sont pas effacés");
    }
  };
  static CleanupCheck verifier;
  AutoCounter() : id(count++) {
    verifier.add(this); // Register itself
    std::cout << "created[" << id << "]" 
              << std::endl;
  }
  // Empêche l'affectation et la construction de copie:
  AutoCounter(const AutoCounter&);
  void operator=(const AutoCounter&);
public:
  // Vous pouvez seulement créer des objets avec cela:
  static AutoCounter* create() { 
    return new AutoCounter();
  }
  ~AutoCounter() {
    std::cout << "destroying[" << id 
              << "]" << std::endl;
    verifier.remove(this);
  }
  // Affiche les objets et les pointeurs:
  friend std::ostream& operator<<(
    std::ostream& os, const AutoCounter& ac){
    return os << "AutoCounter " << ac.id;
  }
  friend std::ostream& operator<<(
    std::ostream& os, const AutoCounter* ac){
    return os << "AutoCounter " << ac->id;
  }
}; 
#endif // AUTOCOUNTER_H ///:~

//: C16:AutoCounter.cpp {O}
// Definition des classes membres statiques
#include "AutoCounter.h"
AutoCounter::CleanupCheck AutoCounter::verifier;
int AutoCounter::count = 0;
///:~

//: C16:TPStashTest.cpp
//{L} AutoCounter
#include "AutoCounter.h"
#include "TPStash.h"
#include <iostream>
#include <fstream>
using namespace std;
 
int main() {
  PStash<AutoCounter> acStash;
  for(int i = 0; i < 10; i++)
    acStash.add(AutoCounter::create());
  cout << "Enlève 5 manuellement:" << endl;
  for(int j = 0; j < 5; j++)
    delete acStash.remove(j);
  cout << "En enlève deux sans les effacer:"
       << endl;
  // ... pour générer le message d'erreur de nettoyage.
  cout << acStash.remove(5) << endl;
  cout << acStash.remove(6) << endl;
  cout << "Le destructeur nettoie le reste:"
       << endl;
  // Répete le test des chapitres précédents: 
  ifstream in("TPStashTest.cpp");
  assure(in, "TPStashTest.cpp");
  PStash<string> stringStash;
  string line;
  while(getline(in, line))
    stringStash.add(new string(line));
  // Affiche les chaînes de caractères:
  for(int u = 0; stringStash[u]; u++)
    cout << "stringStash[" << u << "] = "
         << *stringStash[u] << endl;
} ///:~

Revenons sur le cas de la possession. Les conteneurs qui stockent les objets par valeur ne tiennent pas compte de la possession parce qu'ils possèdent clairement l'objet qu'ils contiennent. Mais si votre conteneur stocke des pointeurs (ce qui est plus courant en C++, spécialement avec le polymorphisme), il est alors très probable que ces pointeurs soient aussi utilisés autre part dans le programme, et vous ne voulez pas nécessairement supprimer l'objet parce qu'alors les autres pointeurs du programme référenceraient un objet détruit. Pour éviter ça, vous devez penser à la possession quand vous concevez et utilisez un conteneur.

Beaucoup de programmes sont plus simples que cela et ne rencontrent pas le problème de possession : un conteneur stocke des pointeurs sur des objets qui sont utilisés uniquement par ce conteneur. Dans ce cas la possession est vraiment simple : le conteneur possède ses objets.

La meilleure approche pour gérer le problème de possession est de donner un choix au programmeur client. C'est souvent accompli par un argument du constructeur qui indique par défaut la possession (cas le plus simple). En outre il peut y avoir des fonctions “get” et “set” pour lire et modifier la possession du conteneur. Si le conteneur a des fonctions pour supprimer un objet, l'état de possession affecte généralement cette suppression, et vous pouvez donc trouver des options pour contrôler la destruction dans la fonction de suppression. On peut concevoir que vous puissiez ajouter une donnée de possession pour chaque élément dans le conteneur, de telle sorte que chaque position saurait si elle a besoin d'être détruite ; c'est une variante du compteur de référence, excepté que le conteneur et non l'objet connait le nombre de références pointant sur un objet.

//: C16:OwnerStack.h
// Stack avec contrôle de possession à l'exécution
#ifndef OWNERSTACK_H
#define OWNERSTACK_H
 
template<class T> class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt) 
      : data(dat), next(nxt) {}
  }* head;
  bool own;
public:
  Stack(bool own = true) : head(0), own(own) {}
  ~Stack();
  void push(T* dat) {
    head = new Link(dat,head);
  }
  T* peek() const { 
    return head ? head->data : 0; 
  }
  T* pop();
  bool owns() const { return own; }
  void owns(bool newownership) {
    own = newownership;
  }
  // Auto-conversion de type : vrai si pas vide :
  operator bool() const { return head != 0; }
};
 
template<class T> T* Stack<T>::pop() {
  if(head == 0) return 0;
  T* result = head->data;
  Link* oldHead = head;
  head = head->next;
  delete oldHead;
  return result;
}
 
template<class T> Stack<T>::~Stack() {
  if(!own) return;
  while(head)
    delete pop();
}
#endif // OWNERSTACK_H ///:~

Le comportement par défaut pour le conteneur est de détruire ses objets, mais vous pouvez le changer soit en modifiant l'argument du constructeur soit en utilisant les fonctions membres owns( ) de lecture/écriture.

Comme avec le plus grand nombre de templates que vous êtes susceptibles de voir, toute l'implémentation est contenue dans le fichier d'en-tête. Voici un petit test qui exerce les facultés de possession :

//: C16:OwnerStackTest.cpp
//{L} AutoCounter 
#include "AutoCounter.h"
#include "OwnerStack.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
 
int main() {
  Stack<AutoCounter> ac; // possession activée
  Stack<AutoCounter> ac2(false); // Désactive la possession
  AutoCounter* ap;
  for(int i = 0; i < 10; i++) {
    ap = AutoCounter::create();
    ac.push(ap);
    if(i % 2 == 0)
      ac2.push(ap);
  }
  while(ac2)
    cout << ac2.pop() << endl;
  // Pas de destruction nécessaire puisque
  // ac "possède" tous les objets
} ///:~

L'objet ac2 ne possède pas les objets que vous mettez dedans, ainsi ac est le conteneur “maître” qui prend la responsabilité de la possession. Si, à un moment quelconque de la durée de vie du conteneur, vous voulez changer le fait que le conteneur possède ses objets, vous pouvez le faire en utilisant owns( ).

Il serait aussi possible aussi de changer la granularité de la possession afin qu'elle soit définie objet par objet, mais cela rendra probablement la solution au problème de possession plus complexe que le problème lui-même.

En fait, créer une copie des objets dans un conteneur générique est un problème complexe si vous n'avez pas les templates. Avec les templates, ces choses sont relativement simples – vous dites juste que vous stockez des objets plutôt que des pointeurs :

//: C16:ValueStack.h
// Stockage d'objets par valeur dans une pile
#ifndef VALUESTACK_H
#define VALUESTACK_H
#include "../require.h"
 
template<class T, int ssize = 100>
class Stack {
  // Le constructeur par défaut effectue
  // l'initialisation de chaque élément dans le tableau :
  T stack[ssize];
  int top;
public:
  Stack() : top(0) {}
  // Le constructeur pa recopie copie les objets dans le tableau :
  void push(const T& x) {
    require(top < ssize, "Too many push()es");
    stack[top++] = x;
  }
  T peek() const { return stack[top]; }
  // L'Objet existe encore quand vous le dépilez ; 
  // il est seulement plus disponible :
  T pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
};
#endif // VALUESTACK_H ///:~

Le constructeur par recopie pour l'objet contenu effectue la majorité du travail en passant et retournant les objets par valeur. À l'intérieur de push( ), le stockage de l'objet dans la table de la Pile est accompli avec T::operator=. Pour garantir que ceci fonctionne, une classe appelée SelfCounter garde la trace des créations d'objets et des constructeurs par recopie :

//: C16:SelfCounter.h
#ifndef SELFCOUNTER_H
#define SELFCOUNTER_H
#include "ValueStack.h"
#include <iostream>
 
class SelfCounter {
  static int counter;
  int id;
public:
  SelfCounter() : id(counter++) {
    std::cout << "Created: " << id << std::endl;
  }
  SelfCounter(const SelfCounter& rv) : id(rv.id){
    std::cout << "Copied: " << id << std::endl;
  }
  SelfCounter operator=(const SelfCounter& rv) {
    std::cout << "Assigned " << rv.id << " to " 
              << id << std::endl;
    return *this;
  }
  ~SelfCounter() {
    std::cout << "Destroyed: "<< id << std::endl;
  }
  friend std::ostream& operator<<( 
    std::ostream& os, const SelfCounter& sc){
    return os << "SelfCounter: " << sc.id;
  }
};
#endif // SELFCOUNTER_H ///:~
 
//: C16:SelfCounter.cpp {O}
#include "SelfCounter.h"
int SelfCounter::counter = 0; ///:~
 
//: C16:ValueStackTest.cpp
//{L} SelfCounter
#include "ValueStack.h"
#include "SelfCounter.h"
#include <iostream>
using namespace std;
 
int main() {
  Stack<SelfCounter> sc;
  for(int i = 0; i < 10; i++)
    sc.push(SelfCounter());
  // peek() possible, le résultat est un temporaire :
  cout << sc.peek() << endl;
  for(int k = 0; k < 10; k++)
    cout << sc.pop() << endl;
} ///:~

Quand un conteneur Stack est créé, le constructeur par défaut de l'objet contenu est appelé pour chaque objet dans le tableau. Vous verrez initialement 100 objets SelfCounter créés pour raison apparente, mais c'est juste l'initialisation du tableau. Cela peut être un peu onéreux, mais il n'y a pas d'autre façon de faire dans une conception simple comme celle-ci. Une situation bien plus complexe surgit si vous rendez Stack plus générale en permettant à la taille d'augmenter dynamiquement, parce que dans l'implémentation montrée précédemment ceci impliquerait de créer un nouveau tableau (plus large), en copiant l'ancien tableau dans le nouveau, et en détruisant l'ancien tableau (ceci est, en fait, ce que fait la classe vector de la librairie standard C++).

Un itérateur est un objet qui parcourt un conteneur d'autres objets et en sélectionne un à la fois, sans fournir d'accès direct à l'implémentation de ce conteneur. Les itérateurs fournissent une manière standardisée d'accéder aux éléments, qu'un conteneur fournisse ou non un moyen d'accéder directement aux éléments. Vous verrez les itérateurs utilisés le plus souvent en association avec des classes conteneurs, et les itérateurs sont un concept fondamental dans la conception et l'utilisation des conteneurs standards du C++, qui sont complètement décrits dans le Volume 2 de ce livre (téléchargeable à www.BruceEckel.com). Un itérateur est également une sorte de modèle de conception, qui est le sujet d'un chapitre du Volume 2.

De bien des façons, un itérateur est un “pointeur futé”, et vous noterez en fait que les itérateurs imitent généralement la plupart des opérations des pointeurs. Contrairement à un pointeur, toutefois, l'itérateur est conçu pour être sûr, et il est donc moins probable que vous fassiez l'équivalent d'excéder les limites d'un tableau (ou si vous le faites, vous le découvrez plus facilement).

Considérez le premier exemple dans ce chapitre. Le voilà, avec un simple itérateur ajouté :

//: C16:IterIntStack.cpp
// Pile simple d'entiers avec des itérateurs
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;
 
class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  friend class IntStackIter;
};
 
// Un itérateur est comme un pointeur "futé" :
class IntStackIter {
  IntStack& s;
  int index;
public:
  IntStackIter(IntStack& is) : s(is), index(0) {}
  int operator++() { // Prefix
    require(index < s.top, 
      "iterator moved out of range");
    return s.stack[++index];
  }
  int operator++(int) { // Postfix
    require(index < s.top, 
      "iterator moved out of range");
    return s.stack[index++];
  }
};
 
int main() {
  IntStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Traverse avec un itérateur:
  IntStackIter it(is);
  for(int j = 0; j < 20; j++)
    cout << it++ << endl;
} ///:~

Le IntStackIter a été créé pour fonctionner seulement avec un IntStack. Notez que IntStackIter est un friend de IntStack, ce qui lui donne accès à tous les éléments private de IntStack.

Comme un pointeur, le travail de IntStackIter et de se déplacer dans un IntStack et de récupérer des valeurs. Dans cet exemple simple, le IntStackIter ne peut se déplacer que vers l'avant (utilisant les deux formes, pre- et postfixée, de operator++). Toutefois, il n'y a pas de limite à la façon dont un itérateur peut être défini, autre que celles imposées par les contraintes du conteneur avec lequel il travaille. Il est tout à fait acceptable pour un itérateur (dans les limites du conteneur sous-jacent) de se déplacer de n'importe quelle façon au sein de son conteneur associé et d'être à l'origine de modifications des valeurs contenues.

Il est habituel qu'un itérateur soit créé avec un constructeur qui l'attache à un unique conteneur d'objets, et que l'itérateur ne soit pas attaché à un autre conteneur pendant sa durée de vie. (Les itérateurs sont souvent petits et peu coûteux, et vous pouvez donc facilement en faire un autre.)

Avec l'itérateur, vous pouvez traverser les éléments de la pile sans les dépiler, exactement de la même façon qu'un pointeur qui peut se déplacer à travers les éléments d'un tableau. Toutefois, l'itérateur connait la structure sous-jacente de la pile et comment traverser les éléments, et donc bien que vous vous déplaciez comme si vous “incrémentiez un pointeur”, ce qui se déroule en dessous est plus compliqué. C'est la clef des itérateurs : ils abstraient le processus complexe du déplacement d'un élément d'un conteneur au suivant en quelque chose qui ressemble à un pointeur. Le but est que chaque itérateur dans votre programme ait la même interface si bien que n'importe quel code qui utilise l'itérateur n'ait pas à se soucier de ce vers quoi il pointe – il sait juste qu'il peut repositionner tous les itérateurs de la même façon, et le conteneur vers lequel pointe l'itérateur n'a pas d'importance. De cette façon, vous pouvez écrire du code plus générique. Tous les conteneurs et algorithmes dans la bibliothèque standard du C++ sont basés sur ce principe d'itérateurs.

Pour aider à faire des choses plus génériques, il serait pratique d'être capable de dire “chaque conteneur a une classe associée appelée iterator, « mais cela causera généralement des problèmes de noms. La solution est d'ajouter une classe iterator imbriquée à chaque conteneur (remarquez que dans ce cas, « iterator” commence par une minuscule afin de se conformer au style de la bibliothèque standard du C++). Voici IterIntStack.cpp avec un iterator imbriqué :

//: C16:NestedIterator.cpp
// Imbriquer un itérateur dans le conteneur
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
#include <string>
using namespace std;
 
class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  class iterator;
  friend class iterator;
  class iterator {
    IntStack& s;
    int index;
  public:
    iterator(IntStack& is) : s(is), index(0) {}
    // Pour créer l'itérateur surveillant la fin :
    iterator(IntStack& is, bool) 
      : s(is), index(s.top) {}
    int current() const { return s.stack[index]; }
    int operator++() { // Prefix
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[++index];
    }
    int operator++(int) { // Postfix
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[index++];
    }
    // Déplace un itérateur vers l'avant
    iterator& operator+=(int amount) {
      require(index + amount < s.top,
        "IntStack::iterator::operator+=() "
        "tried to move out of bounds");
      index += amount;
      return *this;
    }
    // Pour voir sivous êtes au bout :
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
    friend ostream& 
    operator<<(ostream& os, const iterator& it) {
      return os << it.current();
    }
  };
  iterator begin() { return iterator(*this); }
  // Créer la "sentinelle de fin" :
  iterator end() { return iterator(*this, true);}
};
 
int main() {
  IntStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  cout << "Traverse the whole IntStack\n";
  IntStack::iterator it = is.begin();
  while(it != is.end())
    cout << it++ << endl;
  cout << "Traverse a portion of the IntStack\n";
  IntStack::iterator 
    start = is.begin(), end = is.begin();
  start += 5, end += 15;
  cout << "start = " << start << endl;
  cout << "end = " << end << endl;
  while(start != end)
    cout << start++ << endl;
} ///:~

Quand vous créez une classe friend imbriquée, vous devez suivre la procédure qui consiste à déclarer d'abord le nom de la classe, puis de la déclarer comme une friend, enfin de définir la classe. Autrement, le compilateur sera perdu.

De nouveaux trucs ont été ajoutés à l'itérateur. La fonction membre current( ) produit l'élément du conteneur que sélectionne actuellement l'itérateur. Vous pouvez faire “sauter” un itérateur vers l'avant d'un nombre arbitraire d'éléments en utilisant operator+=. Vous verrez également deux opérateurs surchargés : == et != qui compareront un itérateur avec un autre. Ils peuvent comparer n'importe quel couple de IntStack::iterator, mais ils sont avant tout destinés à vérifier si un itérateur est à la fin d'une séquence, de la même façon dont les itérateurs de la “vraie” bibliothèque standard du C++ le font. L'idée est que deux itérateurs définissent un intervalle, incluant le premier élément pointé par le premier itérateur jusqu'au dernier élément pointé par le deuxième itérateur, sans l'inclure. Donc si vous voulez vous déplacer dans l'intervalle défini par les deux itérateurs, vous dites quelque chose comme :

  while(start != end)
  cout << start++ << endl;

où start et end sont les deux itérateurs dans l'intervalle. Notez que l'itérateur end, auquel nous nous référons souvent comme à la sentinelle de la fin, n'est pas déréférencé et est ici pour vous dire que vous êtes à la fin de la séquence. Ainsi il représente “un pas après la fin”.

La plupart du temps, vous voudrez vous déplacer à travers toute la séquence d'un conteneur, et le conteneur a donc besoin d'un moyen de produire les itérateurs indiquant le début de la séquence et la sentinelle de la fin. Ici, comme dans la bibliothèque standard du C++, ces itérateurs sont produits par les fonctions membres du conteneur begin( ) et end( ). begin( ) utilise le premier constructeur de iterator qui pointe par défaut au début du conteneur (c'est le premier élément poussé sur la pile). Toutefois un second constructeur, utilisé par end( ), est nécessaire pour créer l' iterator sentinelle de la fin. Être “à la fin” signifie pointer vers le haut de la pile, parce que top indique toujours le prochain espace disponible – mais non utilisé – sur la pile. Ce constructeur d' iterator prend un second argument du type bool, qui est un argument factice pour distinguer les deux constructeurs.

Les nombres Fibonacci sont utilisés à nouveau pour remplir le IntStack dans main( ), et les iterator sont utilisés pour se déplacer à travers tout le IntStack ainsi que dans un intervalle étroit de la séquence.

L'étape suivante, bien sûr, est de rendre le code général en le transformant en template sur le type qu'il contient, afin qu'au lieu d'être forcé à contenir uniquement des int vous puissiez stocker n'importe quel type :

//: C16:IterStackTemplate.h
// Template de pile simple avec itérateur imbriqué
#ifndef ITERSTACKTEMPLATE_H
#define ITERSTACKTEMPLATE_H
#include "../require.h"
#include <iostream>
 
template<class T, int ssize = 100>
class StackTemplate {
  T stack[ssize];
  int top;
public:
  StackTemplate() : top(0) {}
  void push(const T& i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  T pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  class iterator; // Déclaration requise
  friend class iterator; // Faites-en un ami
  class iterator { // A présent définissez-le
    StackTemplate& s;
    int index;
  public:
    iterator(StackTemplate& st): s(st),index(0){}
    // pour créer l'itérateur "sentinelle de fin" :
    iterator(StackTemplate& st, bool) 
      : s(st), index(s.top) {}
    T operator*() const { return s.stack[index];}
    T operator++() { // Forme préfixe 
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[++index];
    }
    T operator++(int) { // Forme postfix 
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[index++];
    }
    // Fait avancer un itérateur
    iterator& operator+=(int amount) {
      require(index + amount < s.top,
        " StackTemplate::iterator::operator+=() "
        "tried to move out of bounds");
      index += amount;
      return *this;
    }
    // Pour voir si vous êtes à la fin :
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
    friend std::ostream& operator<<(
      std::ostream& os, const iterator& it) {
      return os << *it;
    }
  };
  iterator begin() { return iterator(*this); }
  // Crée la "sentinelle de la fin" :
  iterator end() { return iterator(*this, true);}
};
#endif // ITERSTACKTEMPLATE_H ///:~

Vous pouvez voir que la transformation d'une classe normale en un template est relativement claire. Cette approche qui consiste à créer et déboguer d'abord une classe ordinaire, puis d'en faire un template, est généralement considérée plus simple que de créer le template à partir de rien.

Notez qu'au lieu de dire simplement :

friend iterator; // Faites-en un ami

Ce code a :

friend class iterator; // Faites-en un ami

C'est important parce que le nom “iterator” est déjà dans la portée, depuis un fichier inclus.

Au lieu de la fonction membre current( ), l' iterator a un operator* pour sélectionner le membre courant, qui fait plus ressembler l'itérateur à un pointeur. C'est une pratique commune.

Voici l'exemple révisé pour tester le template :

//: C16:IterStackTemplateTest.cpp
//{L} fibonacci
#include "fibonacci.h"
#include "IterStackTemplate.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
 
int main() {
  StackTemplate<int> is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Traverse avec un iterateur :
  cout << "Traverse the whole StackTemplate\n";
  StackTemplate<int>::iterator it = is.begin();
  while(it != is.end())
    cout << it++ << endl;
  cout << "Traverse a portion\n";
  StackTemplate<int>::iterator 
    start = is.begin(), end = is.begin();
  start += 5, end += 15;
  cout << "start = " << start << endl;
  cout << "end = " << end << endl;
  while(start != end)
    cout << start++ << endl;
  ifstream in("IterStackTemplateTest.cpp");
  assure(in, "IterStackTemplateTest.cpp");
  string line;
  StackTemplate<string> strings;
  while(getline(in, line))
    strings.push(line);
  StackTemplate<string>::iterator 
    sb = strings.begin(), se = strings.end();
  while(sb != se)
    cout << sb++ << endl;
} ///:~

La première utilisation de l'itérateur se déplace simplement du début à la fin (et montre que la sentinelle de fin fonctionne correctement). Dans la deuxième utilisation, vous pouvez voir comment les itérateurs vous permettent de spécifier facilement un intervalle d'éléments (les conteneurs et les itérateurs dans la bibliothèque standard du C++ utilisent ce concept d'intervalle presque partout). Le operator+= surchargé déplace les itérateurs start et end vers des positions situées au milieu de l'intervalle des éléments dans is, et ces éléments sont affichés. Notez dans la sortie que la sentinelle n'est pas incluse dans l'intervalle, ainsi elle peut se trouver un cran au-delà de la fin pour vous faire savoir que vous avez passé la fin – mais vous ne déréférencez pas la sentinelle de fin, ou sinon vous pouvez finir par déréférencer un pointeur nul. (J'ai mis une garde dans le StackTemplate::iterator, mais il n'y a pas de code de ce genre dans les conteneurs et les itérateurs de la bibliothèque standard du C++ – pour des raisons d'efficacité – et vous devez donc faire attention.)

Finalement, pour vérifier que le StackTemplate fonctionne avec des objets de classes, on en instancie un pour string et on le remplit de lignes du fichier de code source, qui sont ensuite affichées.

XVII-G-1. Stack avec itérateurs▲

//: C16:TStack2.h
// Stack rendue template avec itérateur imbriqué
#ifndef TSTACK2_H
#define TSTACK2_H
 
template<class T> class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt)
      : data(dat), next(nxt) {}
  }* head;
public:
  Stack() : head(0) {}
  ~Stack();
  void push(T* dat) {
    head = new Link(dat, head);
  }
  T* peek() const { 
    return head ? head->data : 0;
  }
  T* pop();
  // Classe iterator imbriquée :
  class iterator; // Déclaration requise
  friend class iterator; // En fait un friend
  class iterator { // Le définit maintenant
    Stack::Link* p;
  public:
    iterator(const Stack<T>& tl) : p(tl.head) {}
    // Constructeur par recopie :
    iterator(const iterator& tl) : p(tl.p) {}
    // Itérateur sentinelle de fin :
    iterator() : p(0) {}
    // operator++ retourne un booléen indiquant la fin :
    bool operator++() {
      if(p->next)
        p = p->next;
      else p = 0; // Indique la fin de la liste
      return bool(p);
    }
    bool operator++(int) { return operator++(); }
    T* current() const {
      if(!p) return 0;
      return p->data;
    }
    // opérateur de déréférencement de pointeur :
    T* operator->() const { 
      require(p != 0, 
        "PStack::iterator::operator->returns 0");
      return current(); 
    }
    T* operator*() const { return current(); }
    // Conversion en bool pour test conditionnel :
    operator bool() const { return bool(p); }
    // Comparaison pour tester la fin :
    bool operator==(const iterator&) const {
      return p == 0;
    }
    bool operator!=(const iterator&) const {
      return p != 0;
    }
  };
  iterator begin() const { 
    return iterator(*this); 
  }
  iterator end() const { return iterator(); }
};
 
template<class T> Stack<T>::~Stack() {
  while(head)
    delete pop();
}
 
template<class T> T* Stack<T>::pop() {
  if(head == 0) return 0;
  T* result = head->data;
  Link* oldHead = head;
  head = head->next;
  delete oldHead;
  return result;
}
#endif // TSTACK2_H ///:~

//: C16:TStack2Test.cpp
#include "TStack2.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
 
int main() {
  ifstream file("TStack2Test.cpp");
  assure(file, "TStack2Test.cpp");
  Stack<string> textlines;
  // Lit le fichier et stocke les lignes dans la Stack :
  string line;
  while(getline(file, line))
    textlines.push(new string(line));
  int i = 0;
  // Utilise l'iterateur pour afficher les lignes de la liste :
  Stack<string>::iterator it = textlines.begin();
  Stack<string>::iterator* it2 = 0;
  while(it != textlines.end()) {
    cout << it->c_str() << endl;
    it++;
    if(++i == 10) // se souvenir de la 10e ligne
      it2 = new Stack<string>::iterator(it);
  }
  cout << (*it2)->c_str() << endl;
  delete it2;
} ///:~

XVII-G-2. PStash avec les itérateurs▲

//: C16:TPStash2.h
// PStash rendu template avec itérateur imbriqué
#ifndef TPSTASH2_H
#define TPSTASH2_H
#include "../require.h"
#include <cstdlib>
 
template<class T, int incr = 20>
class PStash {
  int quantity;
  int next;
  T** storage;
  void inflate(int increase = incr);
public:
  PStash() : quantity(0), storage(0), next(0) {}
  ~PStash();
  int add(T* element);
  T* operator[](int index) const;
  T* remove(int index);
  int count() const { return next; }
  // Classe itérateur imbriquée :
  class iterator; // Declaration requise
  friend class iterator; // En fait un ami
  class iterator { // A présent le définit
    PStash& ps;
    int index;
  public:
    iterator(PStash& pStash)
      : ps(pStash), index(0) {}
    // Pour créer la sentinelle de fin :
    iterator(PStash& pStash, bool)
      : ps(pStash), index(ps.next) {}
    // Constructeur par recopie :
    iterator(const iterator& rv)
      : ps(rv.ps), index(rv.index) {}
    iterator& operator=(const iterator& rv) {
      ps = rv.ps;
      index = rv.index;
      return *this;
    }
    iterator& operator++() {
      require(++index <= ps.next,
        "PStash::iterator::operator++ "
        "moves index out of bounds");
      return *this;
    }
    iterator& operator++(int) {
      return operator++();
    }
    iterator& operator--() {
      require(--index >= 0,
        "PStash::iterator::operator-- "
        "moves index out of bounds");
      return *this;
    }
    iterator& operator--(int) { 
      return operator--();
    }
    // Déplace l'itérateur vers l'avant ou l'arrière :
    iterator& operator+=(int amount) {
      require(index + amount < ps.next && 
        index + amount >= 0, 
        "PStash::iterator::operator+= "
        "attempt to index out of bounds");
      index += amount;
      return *this;
    }
    iterator& operator-=(int amount) {
      require(index - amount < ps.next && 
        index - amount >= 0, 
        "PStash::iterator::operator-= "
        "attempt to index out of bounds");
      index -= amount;
      return *this;
    }
    // Crée un nouvel itérateur qui est déplacé vers l'avant
    iterator operator+(int amount) const {
      iterator ret(*this);
      ret += amount; // op+= does bounds check
      return ret;
    }
    T* current() const {
      return ps.storage[index];
    }
    T* operator*() const { return current(); }
    T* operator->() const { 
      require(ps.storage[index] != 0, 
        "PStash::iterator::operator->returns 0");
      return current(); 
    }
    // Supprime l'élément courant :
    T* remove(){
      return ps.remove(index);
    }
    // Test de comparaison pour la fin :
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
  };
  iterator begin() { return iterator(*this); }
  iterator end() { return iterator(*this, true);}
};
 
// Destruction des objets contenus :
template<class T, int incr>
PStash<T, incr>::~PStash() {
  for(int i = 0; i < next; i++) {
    delete storage[i]; // Pointeurs nuls OK
    storage[i] = 0; // Juste pour être sûr
  }
  delete []storage;
}
 
template<class T, int incr>
int PStash<T, incr>::add(T* element) {
  if(next >= quantity)
    inflate();
  storage[next++] = element;
  return(next - 1); // Numéro de l'index
}
 
template<class T, int incr> inline
T* PStash<T, incr>::operator[](int index) const {
  require(index >= 0,
    "PStash::operator[] index negative");
  if(index >= next)
    return 0; // Pour indiquer la fin
  require(storage[index] != 0, 
    "PStash::operator[] returned null pointer");
  return storage[index];
}
 
template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
  // operator[] vérifie la validité :
  T* v = operator[](index);
  // "Supprime" le pointeur:
  storage[index] = 0;
  return v;
}
 
template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
  const int tsz = sizeof(T*);
  T** st = new T*[quantity + increase];
  memset(st, 0, (quantity + increase) * tsz);
  memcpy(st, storage, quantity * tsz);
  quantity += increase;
  delete []storage; // Vieux stockage
  storage = st; // Pointe vers le nouvel emplacement
}
#endif // TPSTASH2_H ///:~

//: C16:TPStash2Test.cpp
#include "TPStash2.h"
#include "../require.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
class Int {
  int i;
public:
  Int(int ii = 0) : i(ii) {
    cout << ">" << i << ' ';
  }
  ~Int() { cout << "~" << i << ' '; }
  operator int() const { return i; }
  friend ostream&
    operator<<(ostream& os, const Int& x) {
      return os << "Int: " << x.i;
  }
  friend ostream&
    operator<<(ostream& os, const Int* x) {
      return os << "Int: " << x->i;
  }
};
 
int main() {
  { // Pour forcer l'appel au destructeur 
    PStash<Int> ints;
    for(int i = 0; i < 30; i++)
      ints.add(new Int(i));
    cout << endl;
    PStash<Int>::iterator it = ints.begin();
    it += 5;
    PStash<Int>::iterator it2 = it + 10;
    for(; it != it2; it++)
      delete it.remove(); // suppression par défaut
    cout << endl;
    for(it = ints.begin();it != ints.end();it++)
      if(*it) // Remove() provoque des "trous"
        cout << *it << endl;
  } // Destructeur de "ints" appelé ici
  cout << "\n-------------------\n";  
  ifstream in("TPStash2Test.cpp");
  assure(in, "TPStash2Test.cpp");
  // Instancié pour String:
  PStash<string> strings;
  string line;
  while(getline(in, line))
    strings.add(new string(line));
  PStash<string>::iterator sit = strings.begin();
  for(; sit != strings.end(); sit++)
    cout << **sit << endl;
  sit = strings.begin();
  int n = 26;
  sit += n;
  for(; sit != strings.end(); sit++)
    cout << n++ << ": " << **sit << endl;
} ///:~

Jusqu'à maintenant vous avez vu la mécanique des itérateurs, mais comprendre pourquoi ils sont aussi importants nécessite un exemple plus complexe.

Il est courant de voir le polymorphisme, la création d'objets dynamique, et les conteneurs utilisés ensemble dans un vrai programme orienté objet. Les conteneurs et la création dynamique des objets résolvent le problème de ne pas savoir combien ou de quel type d'objets vous aurez besoin. Et si le conteneur est configuré pour contenir des pointeurs vers des objets d'une classe de base, un transtypage a lieu à chaque fois que vous mettez un pointeur vers une classe dérivée dans le conteneur (avec les avantages associés de l'organisation du code et de l'extensibilité). Comme le code final du Volume 1 de ce livre, cet exemple assemblera également les différents aspects de tout ce que vous avez appris jusqu'ici – si vous pouvez suivre cet exemple, alors vous êtes prêt pour le volume 2.

Supposez que vous créez un programme qui permette à l'utilisateur d'éditer et de produire différents types de dessins. Chaque dessin est un objet qui contient une collection d'objets Shape:

//: C16:Shape.h
#ifndef SHAPE_H
#define SHAPE_H
#include <iostream>
#include <string>
 
class Shape {
public:
  virtual void draw() = 0;
  virtual void erase() = 0;
  virtual ~Shape() {}
};
 
class Circle : public Shape {
public:
  Circle() {}
  ~Circle() { std::cout << "Circle::~Circle\n"; }
  void draw() { std::cout << "Circle::draw\n";}
  void erase() { std::cout << "Circle::erase\n";}
};
 
class Square : public Shape {
public:
  Square() {}
  ~Square() { std::cout << "Square::~Square\n"; }
  void draw() { std::cout << "Square::draw\n";}
  void erase() { std::cout << "Square::erase\n";}
};
 
class Line : public Shape {
public:
  Line() {}
  ~Line() { std::cout << "Line::~Line\n"; }
  void draw() { std::cout << "Line::draw\n";}
  void erase() { std::cout << "Line::erase\n";}
};
#endif // SHAPE_H ///:~

Cela utilise la structure classique des fonctions virtuelles dans la classe de base, qui sont redéfinies dans la classe dérivée. Remarquez que la classe Shape inclut un destructeur virtuel, ce que vous devriez automatiquement ajouter à chaque classe dotée de fonctions virtuelles. Si un conteneur stocke des pointeurs ou des références vers des objets Shape, alors quand les destructeurs virtuels sont appelés pour ces objets tout sera proprement nettoyé.

Chaque type de dessin dans l'exemple suivant fait usage d'un type différent de classe conteneur via les templates : PStash et Stack qui ont été définies dans ce chapitre, et la classe vector de la bibliothèque standard du C++. L'utilisation des conteneurs est extrêmement simple, et en général l'héritage ne constitue pas la meilleure approche (la composition paraît plus logique), mais dans le cas présent l'héritage est une approche simple et n'amoindrit pas l'aspect abordé dans l'exemple.

//: C16:Drawing.cpp
#include <vector> // Utilise les vecteurs standard également !
#include "TPStash2.h"
#include "TStack2.h"
#include "Shape.h"
using namespace std;
 
// Un dessin est fondamentalement un conteneur de Shapes :
class Drawing : public PStash<Shape> {
public:
  ~Drawing() { cout << "~Drawing" << endl; }
};
 
// Un Plan est un autre conteneur de Shapes :
class Plan : public Stack<Shape> {
public:
  ~Plan() { cout << "~Plan" << endl; }
};
 
// Un Schematic est un autre conteneur de Shapes :
class Schematic : public vector<Shape*> {
public:
  ~Schematic() { cout << "~Schematic" << endl; }
};
 
// Un template de fonction :
template<class Iter>
void drawAll(Iter start, Iter end) {
  while(start != end) {
    (*start)->draw();
    start++;
  }
}
 
int main() {
  // Chaque type de conteneur a
  // une interface différente :
  Drawing d;
  d.add(new Circle);
  d.add(new Square);
  d.add(new Line);
  Plan p;
  p.push(new Line);
  p.push(new Square);
  p.push(new Circle);
  Schematic s;
  s.push_back(new Square);
  s.push_back(new Circle);
  s.push_back(new Line);
  Shape* sarray[] = { 
    new Circle, new Square, new Line 
  };
  // Les itérateurs et le template de fonction
  // leur permet d'être traité de manière générique :
  cout << "Drawing d:" << endl;
  drawAll(d.begin(), d.end());
  cout << "Plan p:" << endl;
  drawAll(p.begin(), p.end());
  cout << "Schematic s:" << endl;
  drawAll(s.begin(), s.end());
  cout << "Array sarray:" << endl;
  // Fonctionne même avec les tableaux de pointeurs :
  drawAll(sarray, 
    sarray + sizeof(sarray)/sizeof(*sarray));
  cout << "End of main" << endl;
} ///:~

Les différents types de conteneurs contiennent tous des pointeurs vers Shape et des pointeurs pour transtyper des objets des classes dérivées de Shape. Toutefois, grâce au polymorphisme, le comportement correct se produit toujours quand les fonctions virtuelles sont appelées.

Remarquez que sarray, le tableau de Shape* peut aussi être considéré comme un conteneur.

XVII-H-1. Les templates de fonction▲

Les classes conteneurs sont une partie essentielle de la programmation orientée objet. Ils sont une autre manière de simplifier et de dissimuler les détails d'un programme et d'en accélérer le processus de développement. En outre, ils fournissent beaucoup plus de sécurité et de flexibilité en remplaçant les tableaux primitifs et les techniques relativement grossières de structures de données trouvées en C.

Comme le programmeur client a besoin de conteneurs, il est essentiel qu'ils soient faciles à utiliser. C'est là que les template s interviennent. Avec les templates la syntaxe pour la réutilisation du code source (par opposition à la réutilisation du code objet fournie par l'héritage et la composition) devient suffisamment simple pour l'utilisateur novice. De fait, réutiliser du code avec les templates est nettement plus facile que l'héritage et la composition.

Bien que vous ayez appris comment créer des classes de conteneurs et d'itérateurs dans ce livre, il est en pratique beaucoup plus opportun d'apprendre les conteneurs et itérateurs de la bibliothèque standard du C++, puisque vous pouvez vous attendre à ce qu'ils soient disponibles sur chaque compilateur. Comme vous le verrez dans le Volume 2 de ce livre (téléchargeable depuis www.BruceEckel.com), les conteneurs et les algorithmes de la bibliothèque standard du C++ satisferont presque toujours vos besoins et vous n'avez donc pas besoin d'en créer vous-mêmes de nouveaux.

Certaines questions liées à la conception des classes de conteneurs ont été abordées dans ce chapitre, mais vous avez pu deviner qu'ils peuvent aller beaucoup plus loin. Une bibliothèque compliquée de classes de conteneurs peut couvrir toutes sortes d'autres aspects, en incluant le multithreading, la persistance et le ramasse-miettes (garbage collector, ndt).

Les solutions à certains exercices peuvent être trouvées dans le document électronique The Thinking in C++ Annotated Solution Guide, disponible pour une somme modique sur www.BruceEckel.com.

1. Implémentez la hiérarchie du diagramme OShape de ce chapitre.
2. Modifiez le résultat de l'exercice 1 du Chapitre 15 de façon à utiliser Stack et iterator dans TStack2.h au lieu d'un tableau de pointeurs vers Shape. Ajoutez des destructeurs à la hiérarchie de classe afin que vous puissiez voir que les objets Shape sont détruits quand le Stack sort de la portée.
3. Modifiez TPStash.h de telle sorte que la valeur d'incrément utilisée par inflate( ) puisse être changée durant la durée de vie d'un objet conteneur particulier.
4. Modifiez TPStash.h de façon à ce que la valeur d'incrément utilisée par inflate( ) se réajuste automatiquement pour réduire le nombre de fois nécessaires à son appel. Par exemple, à chaque fois qu'elle est appelée, elle pourrait doubler la valeur de l'incrément à utiliser dans l'appel suivant. Démontrez cette fonctionnalité en en rapportant chaque fois qu' inflate( ) est appelée, et écrivez du code test dans main( ).
5. Transformez en template la fonction fibonacci( ) sur le type de valeur qu'elle produit (de façon qu'elle puisse produire des long, des float, etc. au lieu d'uniquement des int).
6. En utilisant la bibliothèque standard du C++ vector comme implémentation sous-jacente, créez une classe template Set qui accepte uniquement un seul de chaque type d'objet que vous placez dedans. Faites une classe iterator imbriquée qui supporte le concept de “sentinelle de fin” développé dans ce chapitre. Écrivez un code de test pour votre Set dans main( ), puis substituez le template set de la bibliothèque standard du C++ pour vérifier que son comportement est correct.
7. Modifiez AutoCounter.h afin qu'il puisse être utilisé comme objet membre au sein de n'importe quelle classe dont vous voulez suivre la création et la destruction. Ajoutez un membre string pour retenir le nom de la classe. Testez cet outil dans une classe de votre cru.
8. Créez une version de OwnerStack.h qui utilise un vector de la bibliothèque standard du C++ comme implémentation sous-jacente. Vous pourriez avoir besoin de chercher certaines des fonctions membres de vector pour ce faire (ou bien regardez simplement le fichier d'en-tête <vector>).
9. Modifiez ValueStack.h de façon à ce qu'elle croisse dynamiquement lorsque vous empilez des objets avec push( ) et qu'elle se trouve à court d'espace. Modifiez ValueStackTest.cpp pour tester la nouvelle fonctionnalité.
10. Répétez l'exercice 9, mais utilisez un vector de la bibliothèque standard du C++ comme implémentation interne de ValueStack. Notez comme s'est plus facile.
11. Modifiez ValueStackTest.cpp de façon à utiliser un vector decla bibliothèque standard du C++ au lieu d'un Stack dans main( ). Notez le comportement à l'exécution : est-ce que le vector crée automatiquement un paquet d'objets par défaut lorsqu'il est créé ?
12. Modifiez TStack2.h de telle sorte qu'elle utilise un vector de la bibliothèque standard du C++ comme implémentation sous-jacente. Assurez-vous que vous ne modifiez pas l'interface, pour que TStack2Test.cpp fonctionne sans modification.
13. Répétez l'exercice 12 en utilisant une stack de la bibliothèque standard du C++ au lieu d'un vector(vous pouvez avoir besoin de chercher de l'information sur stack ou bien d'examiner le fichier d'en-tête <stack>).
14. Modifiez TPStash2.h de telle sorte qu'elle utilise un vector de la bibliothèque standard du C++ comme implémentation sous-jacente. Assurez-vous que vous ne modifiez pas l'interface, pour que TPStash2Test.cpp fonctionne sans modification.
15. Dans IterIntStack.cpp, modifiez IntStackIter pour lui donner un constructeur “sentinelle de fin”, et ajoutez operator== et operator!=. Dans main( ), utilisez un itérateur pour vous déplacer à travers des éléments du conteneur jusqu'à ce que vous ayez atteint la sentinelle de fin.
16. En utilisant TStack2.h, TPStash2.h, et Shape.h, instanciez les conteneurs Stack et PStash pour des Shape*, remplissez-les avec un assortiment de pointeurs Shape upcastés, puis utilisez les itérateurs pour vous déplacer à travers chaque conteneur et appelez draw( ) pour chaque objet.
17. Transformez en template la classe Int dans TPStash2Test.cpp de façon à ce qu'elle puisse contenir n'importe quel type d'objet (sentez-vous libre de modifier le nom de la classe en quelque chose de plus approprié).
18. Transformez en template la classe IntArray dans IostreamOperatorOverloading.cpp du chapitre 12, en paramétrant à la fois le type d'objet qu'elle contient et la taille du tableau interne.
19. Changez ObjContainer(dans NestedSmartPointer.cpp du chapitre 12) en template. Testez avec deux classes différentes.
20. Modifiez C15:OStack.h et C15:OStackTest.cpp en transformant en template la class Stack de telle sorte qu'elle hérite automatiquement de la classe contenue et d' Object(héritage multiple). La Stack générée devrait accepter et produire uniquement des pointeurs du type contenu.
21. Répétez l'exercice 20 en utilisant vector au lieu de Stack.
22. Dérivez une classe StringVector de vector<void*> et redéfinissez les fonctions membres push_back( ) et operator[] pour n'accepter et ne produire que des string*(et réalisez le transtypage approprié). À présent créez un template qui créera automatiquement une classe conteneur pour faire la même chose pour des pointeurs de n'importe quel type. Cette technique est souvent utilisée pour réduire le gonflement de code résultant de nombreuses instanciations de template.
23. Dans TPStash2.h, ajoutez et testez un operator- à PStash::iterator, suivant la logique de operator+.
24. Dans Drawing.cpp, ajoutez et testez une fonction template pour appeler les fonctions membres erase( ).
25. (Avancé) Modifiez la classe Stack dans TStack2.h pour permettre une granularité complète de la propriété : ajoutez un signal à chaque lien pour indiquer si ce lien possède l'objet vers lequel il pointe, et supportez cette information dans la fonction push( ) et dans le destructeur. Ajoutez des fonctions membres pour lire et changer la propriété de chaque lien.
26. (Avancé) Modifiez PointerToMemberOperator.cpp du Chapitre 12 de telle sorte que FunctionObject et operator->* soient des templates qui puissent fonctionner avec n'importe quel type de retour (pour operator->* vous aurez à utilisez des templates membres décrits au volume 2). Ajoutez et testez un support pour zéro, un et deux arguments dans les fonctions membres de Dog.