INTRODUCTION A C++

Préambule

La maîtrise des différents mécanismes offerts par le langage requiert clairement du temps, des efforts et de la pratique. Cependant aucune de ces facilités n'est imposée au programmeur : à de rares exceptions près un programme C est un programme C++, et quiconque connaît C est immédiatement opérationnel en C++. De fait, pour un programmeur C une transition facile et indolore consiste à intégrer graduellement dans son code les constructions et mécanismes propres à C++, au fur et à mesure de ses besoins et de la progression de sa maîtrise du langage. Rien ne force par exemple à utiliser les exceptions, ou à suivre une approche de conception orientée objet. L'utilisation de la bibliothèque standard ne nécessite qu'une compréhension relativement superficielle de la programmation générique.

Lorsque j'ai moi même effectué cette transition de C à C++ j'ai été frappé de voir comment certaines constructions ou facilités de C++ me permettaient de suppléer des insuffisances de C dans la poursuite d'une règle que je m'étais fixé pour le développement et que l'on pourraît exprimer comme suit :

Point d'intervention unique : toute modification, qu'il s'agisse de la valeur d'une constante, du type d'une donnée ou d'un frament d'algorithme, doit pouvoir être effectuée en un point et un seul et se propager automatiquement au reste du code, quelle que soit la taille ou la complexité du projet concerné.

Cette expérience a orienté la structure de ce document. Après quelques rappels on commencera par évoquer en quoi en comment C++ peut être utilisé comme un meilleur C. On abordera ensuite successivement les notion de type utilisateur, de polymorphisme dynamique (la forme la plus courante de la programmation dite orientée objet), et enfin  de programmation générique. 
 

Rappels

Organisation mémoire

Chaque variable ou zone de données utilisée dans un programme réside dans l'une ou l'autre de ces régions :

int i;                         // variable globale (Static Data)
int* ip;                       // variable globale (Static Data)
int it[10];                    // tableau global (Static Data)
int f(int n, double d) {          // n et d résideront dans la pile (Stack)
    int m;                        // variable locale (Stack)
    ip = (int*)malloc(n*sizeof(int)); // la zone mémoire est allouée dans
                                      // le tas. Son adresse est stockée
                                      // dans ip.
    ....
}

Appel de fonctions

Les valeurs temporaires, telles que celles apparaissant lors de l'évaluation d'expressions, peuvent être placées dans la région temporaries. Les variables locales peuvent être placées dans la région local data. La région saved machine status peut recevoir des informations relatives à l'état de la machine juste avant l'invocation de la fonction, telles que la valeur de certains registres ou celle du compteur de programme, qui devront être restaurées au retour de la fonction. La région access link peut faire référence à des données non locales résidant dans d'autres enregistrements d'activation. La région control link pointe sur l'enregistrement d'activation de la fonction appelante. La région actual parameters recoit les valeurs effectives des paramètres utilisés lors d'un appel spécifique, tandis que la région returned value est utilisée pour retourner une valeur à la fonction appelante.

La forme effective de cet enregistrement dépend du compilateur et du niveau d'optimisation. En pratique, la plupart de ces régions peuvent être vides, les informations correspondantes étant passées via des registres. Cette représentation est donc assez théorique, mais permet de se faire une idée de l'origine du coût lié à un appel de fonction.

C++ comme un meilleur C

Commentaires

/* commentaire simple C */
/* commentaire
    multiligne
    de style C */
// commentaire de style C++

#if defined(FOO)
...
#endif /* defined(FOO) */

Déclaration et initialisation

void f(int angle) {
    int i = 0, j;
    char* msg = "hello, world\n";
    double d;
    ...
    j = strlen(msg);
    d = sin(angle);
    for (j = 0; j < i ; j++ ) ...
    ...
}

void f(int angle) {
    int i = 0;
    char const * msg = "hello, world\n";
    int j = strlen(msg);
    double d = sin(angle);
    ...
}

for (int i = 0; i < n; ++i) {
    ... // utilise i
}
// i indéfini ici

if (Foo * fp = make_foo(...)) {
    ... // utilise fp
} else {
    ... // fp indéfini ici
}
... // fp indéfini ici

Plus besoin de typedef pour les struct

struct P2 { int x, y; };

struct P2 f(struct P2 p);   /* style C */

P2 f(P2 p);           // C++

typedef struct sP2 { int x, y; } P2; // plus nécessaire

Passage de paramètres par valeurs

void punition(int n) {
    for ( ; n > 0; --n)
       printf("je ne ferais plus l'andouille en cours\n");
    /* à ce point n vaut 0 */
}

int main() {
    int nlignes = 100;
    punition(nlignes);
    /* à ce point nlignes vaut toujours 100 */
}

struct Matrice { double a11, a12, a13, a21, a22, a23, a31, a32, a33; };
double determinant(struct Matrice m) {
    ...
}

Références et passage de paramètres par référence

void incr(int* ip) { /* version C */
    *ip += 1;
}

void swap(int* ap, int* bp) { /* version C */
    int tmp = *ap; *ap = *bp; *bp = tmp;
}

int i = 2, j = 0;
incr(&i);
/* --> i vaut maintenant 3 */
swap(&i,&j);
/* --> i vaut maintenant 0 et j vaut 3 */

void incr(int& ip) { // version C++
    i += 1;
}

void swap(int& a, int& b) { // version C++
    int tmp = a; a = b; b = tmp;
}

int i = 2, j = 0;
incr(i);
// --> i vaut maintenant 3
swap(i,j);
// --> i vaut maintenant 0 et j vaut 3

int i = 2;
// int& ir;    // ILLEGAL
int& ir = i;   // OK, ir désigne i
int j = ir;    // j vaut maintenant 2
ir = 3;        // modifie i
int* jp = &j;
int& jr = *jp; // OK, jr désigne j

int* kp;       // DANGEREUX (kp est indéfini)
int& kr = *kp; // légal, mais comportement non spécifié à l'exécution

Passage de paramètres par référence à const

typedef struct sMatrice {
    double a11, a12, a21, a22;
} Matrice;

double determinant(Matrice * mp) {
    return mp->a11 * mp->a22 - mp->a21 * mp->a12;
}

struct Matrice {
    double a11, a12, a21, a22;
};

double determinant(Matrice const & m) {
    return m.a11 * m.a22 - m.a21 * m.a12;
}

void f(Matrice const & m) {
    m.a11 = 0; // illégal : on tente de modifier m !
};

Surcharge

int min(int a, int b) {
    return (a < b) ? a : b;
}
float min_f(float a, float b) {
    return (a < b) ? a : b;
}
double min_d(double a, double b) {
    return (a < b) ? a : b;
}

$ gcc -c min.c && nm --extern-only min.o
00000000 T _min
0000003c T _min_d
00000018 T _min_f
$

int min(int a, int b) {
    return (a < b) ? a : b;
}
float min(float a, float b) {
    return (a < b) ? a : b;
}
double min(double a, double b) {
    return (a < b) ? a : b;
}

$ g++ -c min.cc && nm -n --extern-only min.o
00000000 T _min__Fii
0000001c T _min__Fff
00000044 T _min__Fdd
$

$ nm -n --extern-only --demangle min.o
00000000 T min(int, int)
0000001c T min(float, float)
00000044 T min(double, double)
$

Fonctions en ligne (inline)

#define MIN(a,b) (((a) < (b)) ? (a) : (b))
z = MIN(f(x), f(y)); // génère
                     //    z = (((f(x)) < (f(y))) ? (f(x)) : (f(y)))

inline int min(int a, int b) { return a < b ? a : b; }
z = min(f(x), f(y)); // génère un code équivalent à
                     //    int tmp1 = f(x);
                     //    int tmp2 = f(y);
                     //    z = tmp1 < tmp2 ? tmp1 : tmp2;

Patrons (template)

inline void swap(int& a, int& b) {
    int tmp = a; a = b; b = tmp;
}
inline void swap(float& a, float& b) {
    float tmp = a; a = b; b = tmp;
}
inline void swap(double& a, double& b) {
    double tmp = a; a = b; b = tmp;
}

template <class T>
inline void swap(T & a, T & b) {
    T tmp; tmp = a; a = b; b = tmp;
}

int i, j;
double f, g;
...
swap(i,j); // invoque swap<int>
swap(f,g); // invoque swap<double>

template <class T>
inline T min(T a, T b) { return a < b ? a : b; }

int i, j;
double d;
...
i = min(i,j);          // OK, invoque min<int>
d = min(i,d);          // ERREUR
d = min((double)i, d); // OK, invoque min<double>
d = min<double>(i, d); // OK (i est converti en double)
i = min<int>(i,d);     // OK (d est converti en int)

// définit un tuple de N données élémentaires de type T
template <class T, int N>
struct Tuple {
    T rep[N];
};

Tuple<float,3> f;
Tuple<int, 2> g;

// carré de la norme d'un Tuple<T,N>
template <class T, int N>
T sqnorm(Tuple<T,N> const & x) {
    T res = 0;
    for (int i = 0; i < N; ++i) res += x.rep[i];
    return res;
}

template <class T>                  // version générique
inline T min(T a, T b) {
    return a < b ? a : b;
}

inline bool min(bool a, bool b) {   // autre algoritme pour les booleens
    return a & b;
}

Il est par ailleurs possible de spécialiser un template pour un jeu de paramètres particuliers. On y reviendra dans la suite.

En finir avec les macros ?

• efficacité : éviter le coût d'un appel de fonction
• généricité : donner un nom à un algorithme indépendamment du type des données manipulées

#define PLUS(a,b) a + b
i = PLUS(2,3)*PLUS(4,5); // AIE ! i vaut 19...
#define FOIS(a,b) (a*b)
j = FOIS(2+3,4);         // AIE ! j vaut 14...

#define MIN(a,b) (((a) < (b)) ? (a) : (b))
i = 1;
j = MIN(0,--i);          // AIE ! j vaut -1...

c = MIN(f(a),f(b));      // trois appels à f

En C++, les template et la directive inline offrent des alternatives qui satisfont aux exigences précitées d'efficacité et de généricité, et on y utilise normalement beaucoup moins les macros qu'en C.

Fonctions membres

struct Complex {
    double real, imag;           // données membres
    double magnitude() const {   // fonction membre const
        return hypot(real, imag);
    }
    void scale_by(double d) {    // fonction membre non const
        real *= d;
        imag *= d;
    }
    void set_real(double real) {
        this->real = real;
    }
    ...
};

On accède aux fonctions membres avec une syntaxe analogue aux données membres :

Complex c;
c.real = 1.0;
c.imag = 2.0;
Complex *cp = &c;

double r = c.real;          // notation pointée (objets et références)
double m = c.magnitude();
c.scale_by(2.0);

r = cp->real();             // notation fléchée (pointeurs)
m = cp->magnitude();
cp->scale_by(2.0);

extern const Complex c; // peut être en ROM
    ...
    double m = c.magnitude(); // OK, instance const et fonction membre const
    c.scale_by(2.0);          // ILLEGAL, instance const et fonction membre non const

void f(Complex const & x) {
    double m = c.magnitude(); // OK, instance const et fonction membre const
    c.scale_by(2.0);          // ILLEGAL, instance const et fonction membre non const
}

struct Complex {
    double real, imag;           // données membres
    int magnitude() const;       // déclaration de fonction membre
    void scale_by(double d);     // déclaration de fonction membre
    ...
};

double Complex::magnitude() const {     // définition
    return hypot(real, imag);
}

void Complex::scale_by(double d) {      // définition
    real *= d;
    imag *= d;
}

Une fonction membre définie au moment de sa déclaration dans le corps de la classe est implicitement inline.

A ce stade, l'intérêt de définir et d'utiliser une fonction membre plutôt qu'une fonction libre n'est pas flagrant :

double magnitude(Complex const & c) {
   return hypot(c.real, c.imag);
}
m = magnitude(c);   // invocation de la fonction libre
m = c.magnitude();  // invocation de la fonction membre

Entrées/sorties formatées avec les iostream

#include <stdio.h>
int i;
float f;
...
printf("la valeur de i est %d, celle de f est %f", i, f);

Les iostream de C++ permettent d'effectuer des entrées/sorties formatées sans avoir à spécifier de format, grâce aux opérateurs d'insertion << et d'extraction >>. On peut insérer sur un ostream (écriture) et extraire d'un istream (lecture). C++ prédéfinit deux ostream, cout et cerr, qui correspondent respectivement à stdout et stderr de C, et un istream , cin, qui correspond à stdin.  Ils s'utilisent comme suit :

cout << "entrez un nombre : ";
int i;
cin >> i;
cout << "vous avez saisi la valeur " << i << endl;

#include <iostream>
#include <cmath> /* hypot */
struct Pt { int x, y; };
ostream & operator << (ostream & os, Pt const & p) { // opérateur d'insertion pour les Pt
    return cout << "[" << p.x << "," << p.y << "]";
}
int main() {
    Pt p; p.x = 3; p.y = 4;
    cout << "le point " << p << " est à la distance "
         << hypot(p.x, p.y) << " de l'origine" << endl;
    // génère la ligne suivante sur la sortie standard :
    // le point [2,3] est à la distance 5 de l'origine
}

#define SHOW(X) cout << #X << " = " << (X) << endl
    ...
    int a = 2, b = 3;
    Pt p; p.x = 1; p.y = 2;
    SHOW(a);    // génère la ligne   a = 2       sur la sortie standard
    SHOW(a+b);  // génère la ligne   a+b = 5     sur la sortie standard
    SHOW(p);    // génère la ligne   p = [1,2]   sur la sortie standard

Constructeurs

struct P2 { double x, y; };
P2 p;                  // déclaration
p.x = 2.0; p.y = 3.0;  // initialisation

struct P2 {
    double x, y;
    P2(double xx, double yy) { // constructeur à deux paramètres
        x = xx;
        y = yy;
    }
    P2(double diag) {          // constructeur à un paramètre
        x = y = diag;
    }
    P2() {                     // constructeur par défaut (sans paramètre)
        x = y = 0;
    }
    P2(P2 const & rhs) {       // constructeur de copie
        x = rhs.x;
        y = rhs.y;
    }
};

P2 p(2,3);   // utilisation du constructeur à deux paramètres P2::P2(double, double)
P2 q(1);     // utilisation du constructeur à un paramètre P2::P2(double)
P2 r;        // utilisation du constructeur par défault P2::P2()
P2 s(p);     // utilisation du constructeur de copie P2::P2(P2 const &)
P2 t[4];     // chaque élément du tableau est initialisé par le constructeur par défaut

struct L2 {
    P2 a, b;
    L2(P2 const & aa, P2 const & bb) {
        a = aa; b = bb; // inefficace
    }
    ...
};

struct L2 {
    P2 a, b;
    L2(P2 const & aa, P2 const & bb)
        : a(aa), b(bb) // construction directe de a et b par P2::P2(P2 const &)
    {
                       // le corps du constructeur est vide
    }
    ...
};

struct P2 {
    double x, y;
    P2(double xx, double yy) : x(xx), y(yy) {}
    P2(double diag) : x(diag), y(diag) {}
    P2() : x(0), y(0) {}
    P2(P2 const & rhs) : x(rhs.x), y(rhs.y) {}
};

Lorsque le constructeur par défault existe, les initialisations exprimées comme une affectation sont normalement optimisées en un appel direct au constructeur adéquat :

P2 u = 1.0;  // utilisation du constructeur à un paramètre P2::P2(double)
P2 v = u;    // utilisation du constructeur de copie P2::P2(P2 const &)

Destructeur

struct Foo {
    ...
    ~Foo() { ... } // destructeur
};

Affectation

#include <cstring> // strdup()
#include <cstdlib> // free()
struct NaiveString {
    char const * ptr;
    NaiveString(char const * p) : ptr(strdup(p)) {} // constructeur à un paramètre
    ~NaiveString() { free(p); }
    NaiveString const & operator = (NaiveString const & rhs) {
        if (this != &rhs) { // protection contre l'auto-affectation
            free(ptr);
            ptr = strdup(rhs.ptr);
        }
        return *this;
    }
    ...
};

NaiveString a("Hello");
NaiveString b("World");

a = b;

a.operator = (b);

a = (b = c); // réellement a.operator = (b.operator = (c));

NaiveString const & min(NaiveString const & lhs, NaiveString const & rhs) {
    return (strcmp(lhs.ptr, rhs.ptr) < 0) ? lhs : rhs;
}

a = min(a,b);

Allocation dynamique

struct P2 *p = (struct P2 *)malloc(sizeof(struct P2)); /* allocation d'un P2 */
struct P2 *t = (struct P2 *)malloc(sizeof(struct P2) * N); /* allocation d'un tableau de N P2 */

P2* p = new P2;      // allocation, puis initialisation par le constructeur par défaut
P2* q = new P2(1,2); // allocation, puis initialisation par un constructeur
P2* t = new P2[N];   // allocation d'u tableau de N P2, tous initialisés par le constructeur par défaut

delete p;
delete q;
delete [] t;

Membres statiques

struct Counted {
    static int count;
    Counted() { ++count; ... }
    Counted(Counted const & r) { ++ count; ... }
    ~Counted() { --count; ... }
    ...
};

#include "Counted.hh"
int Counted::count = 0;
...

Types utilisateur

Encapsulation : class, public:, private:, friend

La seule différence entre struct et class est l'accessibilité par défaut des membres (données ou fonctions). Il existe trois niveaux d'accessibilité :

• public : les membres public sont accessibles à tous. C'est le mode par défaut pour les struct.
• private : les membres private ne sont accessibles qu'aux fonctions membres de la classe, et aux fonctions et classes amies (friend).
• protected : même restriction que private, sauf pour les classes dérivées.

class Foo {
    int a, b;
public:
    Foo(int, int);
    void bar();
private:
    void baz();
    Foo();
friend ostream & operator << (ostream & os, Foo const & f);
};

ostream & operator << (ostream & os, Foo const & f) {
    return os << f.a   // OK : bien que operator<<(ostream&, Foo const &)
              << " "   // soit une fonction libre, elle est amie de Foo
              << f.b;  // et peut donc accéder aux membres privés a et b
}

    ...
    Foo f(1,2);    // OK, constructeur public
    f.bar();       // OK, fonction membre publique
    f.baz();       // ILLEGAL ! fonction membre privée
    Foo g;         // ILLEGAL ! le constructeur par défaut est privé
    Foo t[4];      // ILLEGAL ! nécessite d'accéder au constructeur par défaut

Une utilisation classique de ces protections est d'interdire la manipulation directe des données membres, en forçant le passage par des accesseurs ou modifieurs. Cela peut permettre le contrôle systématique d'invariants lors des modification. Cela isole par ailleurs l'utilisateur des détails d'implémentation.

template <class _FLT>
class complex
{
public:
  complex (_FLT r = 0, _FLT i = 0): re (r), im (i) { }
  /* ... */
  _FLT real () const { return re; }
  _FLT imag () const { return im; }
private:
  _FLT re, im;
  /* ... */
};

Passage par référence et temporaires

Un exemple complet : arithmétique d'intervalle

Introduction

[a,b] + [c,d] = [a+c,b+d]
[a,b] - [c,d] = [a-d,b-c]
[a,b] * [c,d] = [min(ac,ad,bc,bd),max(ac,ad,bc,bd)]
[a,b] / [c,d] = [a,b] * (1/[c,d])
          {  [1/d,1/c] si 0 < c
1/[c,d] = {  indéfini  si c <= 0 <= d
          {  [1/c,1/d] si d < 0

Dans notre cas, on va donc s'attacher à définir un type intervalle, appelons le IV, et le pourvoir des opérations appropriées. On veut par exemple pouvoir écrire avec des IV comme avec des float

    IV a, b, c, d;                   float a, b, c, d
    ....                             ....
    a = (b + c) * d;                 a = (b + c) * d;

Manifestement, il va falloir un moyen d'expliquer au compilateur comment interpréter x + y si x et y sont des IV.

Mais au fait, qu'est ce que ça va être un IV ? En terme de données on a besoin d'une borne inférieure et d'une borne supérieure. En C, on pourrait créer une struct :

struct IV {
    double l; /* borne inférieure */
    double h; /* borne supérieurs */
};

De l'importance des noms

typedef Borne double;
struct IV {
    Borne l; /* borne inférieure */
    Borne h; /* borne supérieurs */
};

• il n'y a pas de lien immédiatement perceptible entre Borne et IV, c'est dommage, on ne va sans doute se servir de Borne que pour le type IV.
• ce typedef a consommé un nom global (Borne). Pour un petit projet ça ne porte pas à conséquence, mais sur un grand projet ça pourraît être enquiquinant.

typedef IV_Borne double;
struct IV {
    IV_Borne l; /* borne inférieure */
    IV_Borne h; /* borne supérieurs */
};

Non, ce qu'il faudrait en fait, c'est que le typedef soit local au type IV. Surprise ;-) , on peut justement le faire en C++ :

struct IV {
    typedef Borne double;
    Borne l;             // borne inférieure
    Borne h;             // borne supérieurs
};

Voilà une solution élégante : pas de pollution de l'espace global des noms, facilité de maintenance, et en prime pas besoin d'inventer de fastidieuse discipline de nommage. De plus elle se généralise : on pourraît par exemple écrire

struct Vect {
    struct Point {            // local à Vect
        typedef Coord double; // local à Point
        Coord x, y;
    };
    Point a, b;
  };

Le fichier d'entête IV.hh

#ifndef IV_H
#define IV_H

#include <iostream>

// Implémentation naïve d'un type intervalle, doté d'opérations
// arithmétiques :
//  [a,b] + [c,d] = [a+c,b+d]
//  [a,b] - [c,d] = [a-d,b-c]
//  [a,b] * [c,d] = [min(ac,ad,bc,bd),max(ac,ad,bc,bd)]
//  [a,b] / [c,d] = [a,b] * (1/[c,d])
//            {  [1/d,1/c] si 0 < c
//  1/[c,d] = {  indéfini  si c <= 0 <= d
//            {  [1/c,1/d] si d < 0
// une implémentation un peu moins naïve effectuerait lors des
// calculs des arrondis vers l'exterieur (outward rounding), c'est
// à dire vers -infini et +infini pour les bornes inférieure et
// supérieure respectivement.
//
// L'objectif ici est de montrer comment implémenter un type
// numérique "utilisateur", et c'est pourquoi on se contentera de
// cette implémentation naïve.

class IV {
public:

  typedef double Rep;

  class UndefinedInverse {};    // exception locale, levée
                                // en cas de division par zéro

  IV();    // construit [0,0]
  explicit IV(Rep m);           // construit [m,m]
  IV(Rep l, Rep h);             // construit [l,h] (ou [h,l] si h < l)
  IV(IV const & rhs);

  IV const & operator= (IV const & rhs);
  ~IV();

  IV inverse() const;           // inverse
  IV operator-() const;         // moins unaire
  Rep l() const { return m_l; } // borne inférieure de l'intervalle
  Rep h() const { return m_h; } // borne supérieure de l'intervalle

  IV const & operator += (IV const & rhs);
  IV const & operator -= (IV const & rhs);
  IV const & operator *= (IV const & rhs);
  IV const & operator /= (IV const & rhs) { return operator *= (rhs.inverse()); }

private:
  IV const & normalize();       // assure que m_l <= m_h

  Rep m_l, m_h;
};

bool operator == (IV lhs, IV rhs); // vrai si les deux intervalles sont identiques
inline bool operator != (IV lhs, IV rhs) { return !(lhs == rhs); }

inline bool operator == (IV::Rep x, IV i) { // vrai si i est dans l'intervalle x
  return (i.l() <= x) && (x <= i.h());
}
inline bool operator == (IV i, IV::Rep x) { return x == i; } // invoque operator == (IV::Rep, IV)
inline bool operator != (IV::Rep x, IV i) { return !(x == i); }
inline bool operator != (IV i, IV::Rep x) { return !(i == x); }

IV operator+(IV const & lhs, IV const & rhs);
IV operator-(IV const & lhs, IV const & rhs);
IV operator*(IV const & lhs, IV const & rhs);
IV operator/(IV const & lhs, IV const & rhs);

// si les bornes basse et haute diffèrent, produit
// le format 'low:high' sinon produit 'low'
ostream & operator << (ostream & os, IV const & x);

// admet deux formats d'entrée : 'low:high' et 'low'
istream & operator >> (istream & is, IV & x);

#endif /* IV_H */

#ifndef IV_H
#define IV_H
...
#endif /* IV_H */

• fichier a.hh:
...
#include "IV.hh"
...
• fichier b.hh:
...
#include "IV.hh"
...
• fichier b.cc:
...
#include "b.hh"
#include "a.hh"
...

Le corps du fichier proprement dit est consacré à la déclaration de la classe IV, puis de fonctions libres conceptuellement associées à IV. Dans la partie publique, on reconnaît un typedef déjà discuté, une déclaration de classe locale (UndefinedInverse), le groupe constructeurs / opérateur d'affectation / destructeur, des fonctions membres const ( inverse(), operator -(), l(), h() ), des fonctions membres non-const (les opérateurs d'affectation arithmétiques). Dans la partie privée, on trouve une méthode à usage interne et la représentation de la classe. On note que certaines fonctions membres sont définies au moment de leur déclaration, ce qui les rend automatiquement inline. On aurait pu obtenir le même résultat en les définissant en dehors de la classe et en les qualifiant explicitement inline :

class IV {
  ...
  Rep l() const;
  ...
  IV const & operator /= (IV const & rhs);
  ...
};

inline IV::Rep IV::l() const { return m_l; }
inline IV const & IV::operator /= (IV const & rhs) { return operator *= (rhs.inverse()); }
...

On note que les opérations relationnelles et arithmétiques entre IV telles que operator+(IV const & lhs, IV const & rhs) sont déclarées comme des fonctions libres. Grâce à la surcharge ce n'est pas un problème. Elles font partie du périmètre sémantique de IV et il est normal qu'elles soient déclarées dans ce fichier d'entête.

Plus important, seuls les opérateurs d'affectation arithmétiques retournent une référence, tous les autres opérateurs arithmétiques retournent des IV par valeur, y compris les fonctions membres IV::operator -() et IV::inverse(). C'est pratiquement inévitable.

Le fichier de définition IV.cc

#include "IV.hh"
#include <algorithm> // swap
#include <iomanip>

IV::IV()
  : m_l(0)
  , m_h(0)
{
}

IV::IV(Rep m)
  : m_l(m)
  , m_h(m)
{
}

IV::IV(Rep l, Rep h)
  : m_l(l)
  , m_h(h)
{
  normalize();
}

IV::IV(IV const & rhs)
  : m_l(rhs.l())
  , m_h(rhs.h())
{
}

IV const & IV::operator= (IV const & rhs)
{
  //if (this != &rhs) {
  m_l = rhs.l();
  m_h = rhs.h();
  //}
  return *this;
}

IV::~IV()
{
}

IV IV::operator - () const
{
  return IV(-h(),-l());
}

IV IV::inverse() const
{
  if (*this == 0) throw UndefinedInverse();
  return IV(1/l(), 1/h());
}

IV const & IV::normalize()
{
  if (m_l > m_h)
    swap(m_l, m_h);
  return *this;
}

IV const & IV::operator += (IV const & rhs)
{
  m_l += rhs.l();
  m_h += rhs.h();
  return *this;
}

IV const & IV::operator -= (IV const & rhs)
{
  m_l -= rhs.h();
  m_h -= rhs.l();
  return *this;
}

namespace {
    template <class T> inline T min(T a, T b) { return (a < b) ? a : b; }
    template <class T> inline T max(T a, T b) { return (a > b) ? a : b; }
}

IV const & IV::operator *= (IV const & rhs)
{
  Rep tmp_l = min(min(l() * rhs.l(), l() * rhs.h()), min(h() * rhs.l(), h() * rhs.h()));
  Rep tmp_h = max(max(l() * rhs.l(), l() * rhs.h()), max(h() * rhs.l(), h() * rhs.h()));
  m_l = tmp_l;
  m_h = tmp_h;
  return *this;
}

bool operator == (IV lhs, IV rhs)
{
  return (lhs.l() == rhs.l()) && (rhs.h() == lhs.h());
}

IV operator+(IV const & lhs, IV const & rhs) {
  return IV(lhs) += rhs;
}

IV operator-(IV const & lhs, IV const & rhs) {
  return IV(lhs) -= rhs;
}

IV operator*(IV const & lhs, IV const & rhs) {
  return IV(lhs) *= rhs;
}

IV operator/(IV const & lhs, IV const & rhs) {
  return IV(lhs) /= rhs;
}

// si les bornes basse et haute diffèrent, produit
// le format 'low:high' sinon produit 'low'
ostream & operator << (ostream & os, IV const & x)
{
  os <<  x.l();
  if (x.l() != x.h())
    os << ":" << x.h();
  return os;
}

// pour faciliter les entrées, on admet deux formats :
// 'low:high' ou bien 'low'.
// Du coup, cette fonction est un peu compliquée.
// Si la lecture échoue, l'istream sera dans l'état
// 'fail' en sortie
istream & operator >> (istream & is, IV & x)
{
  IV::Rep l;
  if (is >> l) {
    char c;
    if (is >> c) {  // la lecture de c a réussi ...
      if (c == ':') {  // ... on est en format low:high
        IV::Rep h;
        if (is >> h)
          x = IV(l,h);
      } else {
        is.putback(c);
        x = IV(l);
      }
    } else {   // la lecture de c a échoué ...
      if (is.eof()) {  // ... mais ce n'est pas une erreur
                       //     si on est en fin de fichier
          is.clear();  // donc on restaure un état valide
          x = IV(l);
      }
    }
  }
  return is;
}

namespace {
  ...
}

Les opérateurs unaires sont définis à partir des opérateurs d'affectation arithmétique correspondants. On pourrait développer leur définition, par exemple

IV operator+(IV const & lhs, IV const & rhs) {
  IV res = lhs;
  res += rhs;
  return res;
}

IV operator+(IV const & lhs, IV const & rhs) {
  return IV(lhs) += rhs;
}

Cette forme est intéressante dans la mesure ou la sémantique d'addition, qui doit apparaitre dans operator + et operator +=, n'est spécifiée qu'une seule fois (ce qui peut faciliter la maintenance ultérieure). Ceci dit, pour un cas aussi simple la forme suivante serait également tout à fait acceptable :

IV operator+(IV const & lhs, IV const & rhs) {
  return IV(lhs.l() + rhs.l(), lhs.h() + rhs.h());
}

Héritage non polymorphique

struct P2 {
    double x, y;
    P2(double x, double y) : x(x), y(y) {}
    double sqdist() const { // carré de la distance à l'origine
        return x*x + y*y;
    }
};

struct P3 {
    double x, y, z;
    P3(double x, double y, double z) : x(x), y(y), z(z) {}
    double sqdist() const { // carré de la distance à l'origine
        return x*x + y*y + z*z;
    }
};

struct P3 {
    P2 xy;
    double z;
    P3(double x, double y, double z) : xy(x,y), z(z) {}
    double sqdist() const { // carré de la distance à l'origine
        return xy.sqdist() + z*z;
    }
};

P3 a(1,2,3);
a.xy.x = 2;        // lourd
cout << a.xy.y;    // lourd

struct P3 : public P2 {
    double z;
    P3(double x, double y, double z) : P2(x,y), z(z) {}
    double sqdist() const { // carré de la distance à l'origine
        return P2::sqdist() + z*z;
    }
};

Du point de vue occupation mémoire, les deux approches sont équivalentes :

Lorsque l'héritage est public comme ci-dessus, on peut employer un P3 en lieu et place d'un P2. En particulier on peut écrire directement

P3 a(1,2,3);
a.x = 2;
cout << a.y;

P3 a(1,2,3);
P2 *pp2;
pp2 = &a;       // OK
P3 * pp3 = pp2; // OK
P2 t[10];
pp3 = &t[1];    // légal mais potentiellement dangereux...

P3 a(1,2,3);
P2 b = a;    // tronconnage, ou slicing : b reçoit la sous partie P2 de a, soit (1,2).

P3 *pp3 = &a;
double x = pp3->sqdist();   // x vaut 14
P2 *pp2 = &a;
double y = pp2->sqdist();   // x vaut 5

En pratique cette forme d'héritage non polymorphique est peu utilisée.

Polymorphisme dynamique

Introduction

class Animal {
    ...
    void manger();
};
class Vache : public Animal {
    ...
    void manger() { /* broute */ }
};
class Poule : public Animal {
    ...
    void manger() { /* picore */ }
};

void repas_des_fauves() {
    Animal *p;
    pour p pointant successivement sur tous les animaux de la collection faire
        p->manger();
}

Méthodes virtuelles

class Animal { // abstraite, car contient des méthodes virtuelle pures
    ...
    virtual void manger() = 0; // méthode virtuelle pure
};

Animal a;       // illégal
Animal t[10];   // illégal
Animal *p;      // OK

class Vache : public Animal {
    ...
    virtual void manger() { /* broute */ }
};

Vache v(...);    // OK
Animal* p = &v;  // OK
Animal& r = v;   // OK

Vache uneVache(...);
Vache uneAutreVache(...);
Poule unePoule(...);
Animal* pA = & uneVache;
pA->manger();    // invoque Vache::manger sur l'instance uneVache
pA = & uneAutreVache;
pA->manger();    // invoque Vache::manger sur l'instance uneAutreVache
pA = & unePoule;
pA->manger();    // invoque Poule::manger sur l'instance unePoule

Les tables de fonctions virtuelles, ou vtbl, associées aux classes dérivées de Animal ont toutes la même structure : la méthode manger se trouve à la même position dans chacune. L'invocation de la méthode manger à partir d'un pointeur pA sur un Animal procède alors comme suit : on déréférence le pointeur pA pour obtenir le vptr, on trouve l'adresse de la méthode à l'index adéquat (connu du compilateur) dans la vtbl qu'il désigne, et on appelle cette méthode en lui passant la valeur de pA comme adresse de l'instance (paramètre caché this).

Manipulation des instances de classes polymorphiques

class Base {
    ...
    virtual Base* clone() const {
        return new Base(this); // utilise le constructeur de copie de Base
    }
};

class Derived : public Base {
    ...
    virtual Base* clone() const {
        return new Derived(this); // utilise le constructeur de copie de Derived
    }
};
 

Base * pb = new Derived(...);
Base * copie = pb->clone();    // invoquera Derived::clone

class Base {};                         // pas de destructeur virtuel
class Derived : public Base {...};
Base * pb = new Derived(...);
delete pb;                             // MAUVAIS : invoque uniquement ~Base au lieu de ~Derived
 

class Base { virtual ~Base() {}};      // destructeur virtuel
class Derived : public Base {...};
Base * pb = new Derived(...);
delete pb;                             // OK : invoque ~Derived

Exemple : manipulation d'expressions arithmétiques

On s'intéresse à des expressions arithmétiques simples, représentées sous forme d'arbres. Par exemple la figure suivante illustre l'expression 1+2*3 :

Chaque noeud de l'arbre est lui même une expression.

On peut déclarer un type abstrait Expression comme suit (fichier Expression.hh):

#ifndef Expression_H
#define Expression_H

class Expression {
public:
  typedef int Val;
  virtual ~Expression();
  virtual Val eval() const = 0;
};

#endif /* Expression_H */

#include "Expression.hh"

Expression::~Expression() {
}

#include <iostream>
#include "Expression.hh"

extern Expression* f();

int main() {
  Expression * e = f();
  cout << e->eval() << endl;
}

La fonction f() est ici typique d'un processus de production associé, par exemple un analyseur syntaxique, qui fournit l'Expression à exploiter.

Pour fabriquer l'expression 1 + 2*3, on a besoin de représenter les valeurs numériques, les sommes et les produits. On crée trois classes dérivées de Expression,
respectivement Constante, Somme et Produit.

Fichier Constante.hh:

#ifndef Constante_H
#define Constante_H

#include "Expression.hh"

class Constante : public Expression {
  Val value;
public:
  Constante(Val val);
  virtual Val eval() const;
};

#endif /* Constante_H */

#include "Constante.hh"

Constante::Constante(Val v) : value(v) {}

Expression::Val Constante::eval() const { return value; }

#ifndef Somme_H
#define Somme_H

#include "Expression.hh"

class Somme : public Expression {
  Expression* l;
  Expression* r;
public:
  Somme(Expression* l, Expression* r);
  virtual Val eval() const;
};

#endif /* Somme_H */

#include "Somme.hh"

Somme::Somme(Expression* l, Expression* r) : l(l), r(r) {}

Expression::Val Somme::eval() const { return l->eval() + r->eval(); }

#ifndef Produit_H
#define Produit_H

#include "Expression.hh"

class Produit : public Expression {
  Expression* l;
  Expression* r;
public:
  Produit(Expression* l, Expression* r);
  virtual Val eval() const;
};

#endif /* Produit_H */

#include "Produit.hh"

Produit::Produit(Expression* l, Expression* r) : l(l), r(r) {}

Expression::Val Produit::eval() const { return l->eval() * r->eval(); }

#include "Constante.hh"
#include "Somme.hh"
#include "Produit.hh"

Expression * f() {
    static Constante a1(1);
    static Constante a2(2);
    static Constante a3(3);
    static Produit p23(&a2, &a3);
    static Somme s1p23(&a1, &p23);
    return &s1p23;
}

On peut maintenant compiler l'ensemble de ces fichiers. L'exécution du programme de test donne bien la valeur attendue :

$ make
make depend
g++ -Wall -W -pedantic -Werror   -MM Expression.cc Constante.cc Somme.cc Produit.cc f.cc tEX_1.cc  > .depend
make all
g++ -Wall -W -pedantic -Werror -c tEX_1.cc -o tEX_1.o
g++ -Wall -W -pedantic -Werror -c Expression.cc -o Expression.o
g++ -Wall -W -pedantic -Werror -c Constante.cc -o Constante.o
g++ -Wall -W -pedantic -Werror -c Somme.cc -o Somme.o
g++ -Wall -W -pedantic -Werror -c Produit.cc -o Produit.o
g++ -Wall -W -pedantic -Werror -c f.cc -o f.o
g++ tEX_1.o Expression.o Constante.o Somme.o Produit.o f.o -o tEX_1
./tEX_1
7
$

Enrichissement de l'exemple : impression formatée des expressions

Supposons qu'on veuille enrichir les fonctionnalités de nos Expression en les dotant de capacités d'impression formatée, pour pouvoir écrire par exemple (fichier tEX_1.cc)

#include <iostream>
#include "Expression.hh"

extern Expression* f();

int main() {
  Expression * e = f();
  cout << *e << " = " << e->eval() << endl;
}

$ ./tEX_1
(1 + (2 * 3)) = 7
$

#ifndef Expression_H
#define Expression_H

#include <iostream>

class Expression {
public:
  typedef int Val;
  virtual ~Expression();
  virtual Val eval() const = 0;
  virtual ostream& print(ostream & os) const = 0;
};

inline ostream & operator<<(ostream & os, Expression const & e) {
  return e.print(os);
}

#endif /* Expression_H */

#ifndef Constante_H
#define Constante_H

#include "Expression.hh"

class Constante : public Expression {
  Val value;
public:
  Constante(Val val);
  virtual ostream & print(ostream &) const;
  virtual Val eval() const;
};

#endif /* Constante_H */

#include "Constante.hh"

Constante::Constante(Val v) : value(v) {}

ostream & Constante::print(ostream & os) const {
  return os << value;
}

Expression::Val Constante::eval() const { return value; }

Constante c(10);
cout << c;       // OK. invoque operator << (ostream &, Expression const &)

#ifndef Binary_H
#define Binary_H

#include "Expression.hh"

class Binary : public Expression {
protected:
  Expression* l;
  Expression* r;
public:
  Binary(Expression* l, Expression* r);
  virtual char opchar() const = 0;
  virtual ostream & print(ostream &) const;
};

#endif /* Binary_H */

#include "Binary.hh"

Binary::Binary(Expression* l, Expression* r) : l(l), r(r) {}

ostream & Binary::print(ostream & os) const {
  return os << '(' << *l << ' ' << opchar() << ' ' << *r << ')';
}

La classe Somme devient alors (fichier Somme.hh)

#ifndef Somme_H
#define Somme_H

#include "Binary.hh"

class Somme : public Binary {
public:
  Somme(Expression* l, Expression* r);
  virtual char opchar() const;
  virtual Val eval() const;
};

#endif /* Somme_H */

#include "Somme.hh"

Somme::Somme(Expression* l, Expression* r)
    : Binary(l,r) // construction du sous-objet Binary de base
{}

char Somme::opchar() const { return '+'; }

Expression::Val Somme::eval() const { return l->eval() + r->eval(); }

Variations sur l'impression

L'opérateur d'insertion de la section précédente réalise une impression en mode infixe. On pourrait vouloir imprimer en mode préfixé (l'opérateur précède les opérandes) ou postfixé (l'opérateur suit les opérandes) :

infix   : (1 + (2 * 3))
prefix  : + 1 * 2 3
postfix : 1 2 3 * +

int main() {
  Expression * e = f();
  cout << "infix   : " << *e << endl;

  cout << "prefix  : ";
  e->prefix_print(cout);
  cout << endl;

  cout << "postfix : ";
  e->postfix_print(cout);
  cout << endl;

  cout << "eval : " << e->eval() << endl;
}

Pour cela, on peut utiliser des petites classes auxiliaires, telles que prefix et postfix ci après (fichier Expression.hh) :

#ifndef Expression_H
#define Expression_H

#include <iostream>

class Expression {
public:
  typedef int Val;
  virtual ~Expression();
  virtual Val eval() const = 0;
  virtual ostream& infix_print(ostream & os) const = 0;
  virtual ostream& prefix_print(ostream & os) const = 0;
  virtual ostream& postfix_print(ostream & os) const = 0;
};

inline ostream & operator<<(ostream & os, Expression const & e) {
  return e.infix_print(os);
}

struct prefix {
  Expression const & e;
  prefix(Expression const & e) : e(e) {}

  // ici on abuse du mot clé friend pour définir une fonction
  // libre dans le corps de la classe. Elle est du coup inline.
  // C'est une alternative à une définition inline extérieure
  // à la classe comme celle pour Expression ci-dessus.
  friend ostream & operator<<(ostream & os, prefix const & x) {
    return x.e.prefix_print(os);
  }
};

struct postfix {
  Expression const & e;
  postfix(Expression const & e) : e(e) {}
  friend ostream & operator<<(ostream & os, postfix const & x) {
    return x.e.postfix_print(os);
  }
};

#endif /* Expression_H */

#include <iostream>
#include "Expression.hh"

extern Expression* f();

int main() {
  Expression * e = f();
  cout << "infix   : " << *e << endl;
  cout << "prefix  : " << prefix(*e) << endl;
  cout << "postfix : " << postfix(*e) << endl;
  cout << "eval : " << e->eval() << endl;
}

#include "Binary.hh"

Binary::Binary(Expression* l, Expression* r) : l(l), r(r) {}

ostream & Binary::infix_print(ostream & os) const {
  return os << '(' << *l << ' ' << opchar() << ' ' << *r << ')';
}

ostream & Binary::prefix_print(ostream & os) const {
  return os << opchar() << ' ' << prefix(*l) << ' ' << prefix(*r);
}

ostream & Binary::postfix_print(ostream & os) const {
  return os << postfix(*l) << ' ' << postfix(*r) << ' ' << opchar();
}

Gestion de mémoire

Gestion simple

S'il est garanti que l'arbre d'expressions est effectivement un arbre et non un graphe plus général, on peut mettre en place une stratégie selon laquelle chaque noeud non-feuille de l'arbre est propriétaire de ses enfants, et qu'il détruit ces derniers lors de sa propre destruction. Cela implique de n'utiliser que des instances dynamiques
(on ne peut pas les mélanger avec des instances automatiques ou statiques).

Pour implémenter ce mécanisme on ajoute un destructeur explicite à Binary dans Binary.hh:

class Binary : public Expression {
    ...
    virtual ~Binary();
    ...
};

Binary::~Binary() {
  delete l;
  delete r;
}

Expression * f() {
  return new Somme(new Constante(1),
                   new Produit(new Constante(2),
                               new Constante(3)));
}

int main() {
  Expression * e = f();
  cout << "infix   : " << *e << endl;
  cout << "prefix  : " << prefix(*e) << endl;
  cout << "postfix : " << postfix(*e) << endl;
  cout << "eval : " << e->eval() << endl;
  delete e;
}

Comptage de référence

La gestion simple évoquée dans la section précédente convient lorsque les expressions sont représentées par des arbres simples. Elle est cependant inadaptée aux graphes. Par exemple l'expression 2+2*2 peut être réalisée par un graphe acyclique orienté, ou DAG (directed acyclic graph) :

Manifestement la destruction récursive de la section précédente n'est pas adaptée : la Constante 2 serait détruite trois fois...

L'utilisation du comptage de référence permet de pallier ce problème (la section suivante explore une alternative possible). L'idée est de maintenir pour chaque Expression un compte des pointeurs qui la désignent, et de ne la détruire effectivement que lorsque ce compte passe à zéro. Ce comportement peut être implanté par une classe de base (Counted.hh) :

#ifndef Counted_H
#define Counted_H

#include <iostream>

class Counted {
  int refcount;
  int add_reference() {
    return ++refcount;
  }
  int rem_reference() {
    return --refcount;
  }
  friend class CountedPtrBase;
protected:
  Counted() : refcount(0) {}
  virtual ~Counted() {}
};

#endif /* Counted_H */

#ifndef CountedPtr_H
#define CountedPtr_H

#include "Counted.hh"

class CountedPtrBase {
  Counted * pointee;
  void add_reference() const {
    if (pointee) pointee->add_reference();
  }
  void rem_reference() const {
    if (pointee && (pointee->rem_reference() == 0))
 delete pointee;
  }
protected:
  CountedPtrBase(Counted * p)
    : pointee(p) {
    add_reference();
  }
  CountedPtrBase(CountedPtrBase const & p)
    : pointee(p.pointee) {
    add_reference();
  }
  CountedPtrBase const & operator = (CountedPtrBase const & p) {
    // l'ordre des instructions réalise la protection contre l'auto-affectation
    p.add_reference();
    rem_reference();
    pointee = p.pointee;
    return *this;
  }
  ~CountedPtrBase() {
    rem_reference();
  }
  Counted & operator*() const { return *pointee; }
  Counted * operator->() const { return pointee; }
};
 
 

template <class T>
class CountedPtr : public CountedPtrBase {
public:
  CountedPtr(T* p)
    : CountedPtrBase(p)
    {}
  CountedPtr(CountedPtr const & rhs)
    : CountedPtrBase(rhs)
    {}
  template <class U> CountedPtr(CountedPtr<U> const & rhs)
    : CountedPtrBase(rhs.operator->())
    {}
  CountedPtr operator = (CountedPtr const & rhs) {
    return CountedPtrBase::operator=(rhs);
  }
  T & operator*() const {
    return static_cast<T &>(CountedPtrBase::operator *());
  }
  T * operator->() const {
    return static_cast<T *>(CountedPtrBase::operator ->());
  }
};

#endif /* CountedPtr_H */

Il faut cependant garantir qu'on ne puisse pas acquérir un pointeur normal sur une instance. Un premier pas consiste à rendre les constructeurs privés (ou protégés) et à filtrer la création par une fonction de construction :

class Constante : public Expression {
  Val value;
protected:
  Constante(Val val);
  virtual ~Constante();
public:
  ...
  static CountedPtr<Expression> makeConstante(Val val) {
    return new Constante(val);
  }
  ...
};

Evidemment, les noeuds du graphe doivent eux-même accéder à leurs enfant au travers de CountedPtr. Il nous faut modifier tous les constructeurs des opérateurs binaires, à commencer par Binary.hh :

class Binary : public Expression {
protected:
  CountedPtr<Expression> l;
  CountedPtr<Expression> r;
  Binary(CountedPtr<Expression> l, CountedPtr<Expression> r);
  virtual ~Binary() {}
public:
  virtual char opchar() const = 0;
  virtual ostream & infix_print(ostream &) const;
  virtual ostream & prefix_print(ostream &) const;
  virtual ostream & postfix_print(ostream &) const;
};

...

class Somme : public Binary {
protected:
  Somme(CountedPtr<Expression> l, CountedPtr<Expression> r);
  virtual ~Somme();
  ...
};

...

Somme::Somme(CountedPtr<Expression> l, CountedPtr<Expression> r)
  : Binary(l,r)
{
}

CountedPtr<Expression> g() {
  CountedPtr<Expression> p = Constante::makeConstante(2);
  return Somme::makeSomme(p, Produit::makeProduit(p, p));
}

int main() {
  CountedPtr<Expression> e = g();
  cout << "infix   : " << *e << endl;
  cout << "prefix  : " << prefix(*e) << endl;
  cout << "postfix : " << postfix(*e) << endl;
  cout << "eval : " << e->eval() << endl;
}

Utilisation d'un ramasse-miettes (garbage collector)

L'utilisation d'un ramasse-miettes est une alternative à l'utilisation du comptage de références. Un ramasse-miettes est un système capable de détecter si les instances allouées dynamiquement sont référencées, et qui se charge de les désallouer lorsqu'elles ne le sont plus. Le C++ standard ne comprend pas de ramasse-miettes,

Dans notre cas, cela simplifie considérablement la gestion. On peut repartir de la version EX3 et simplement exprimer le fait que les Expressions sont gérées par le ramasse-miettes, ce qui peut s'exprimer très simplement par

#include "gc/gc_cpp.h"

class Expression : public gc { ... };

#include "gc/gc_cpp.h"

class Expression : public gc_cleanup { ... };

class Expression : public gc_cleanup {
public:
  static int count; // nombre d'instances vivantes
  static int alloc; // nombre total d'instances allouées

  Expression() { ++ count; ++alloc; }
  virtual ~Expression() { --count; }
  ...
};

#include <iostream>
#include "Expression.hh"
#include "Constante.hh"
#include "Somme.hh"
#include "gc/gc.h"

extern Expression* f();

Expression * tree(int depth) {
  return ((depth == 0)
   ? (Expression *)(new Constante(1))
   : (Expression *)(new Somme(tree(depth-1), tree(depth-1))));
}

Expression * dag(int depth) {
  if (depth == 0)
    return new Constante(1);
  Expression *e = dag(depth -1);
  return new Somme(e,e);
}

struct sentry {
  ~sentry() {
    cerr << endl << "allocated expressions : " << Expression::alloc << endl;
    for (int i = 0; i < 20; ++i) {
      GC_gcollect();
      cerr << "i " << i << " GC_gc_no " << GC_gc_no << " undestroyed expressions : " << Expression::count << endl;
      if (Expression::count == 0)
 break;
    }
  }
};

// l'objet s sera détruit après exécution de main.
sentry s;

int main() {
  {
    Expression * e = tree(10);
    cerr << "infix   : " << *e << endl;
    cerr << "prefix  : " << prefix(*e) << endl;
    cerr << "postfix : " << postfix(*e) << endl;
    cerr << "eval : " << e->eval() << endl;
  }
  {
    Expression * e = dag(10);
    cerr << "infix   : " << *e << endl;
    cerr << "prefix  : " << prefix(*e) << endl;
    cerr << "postfix : " << postfix(*e) << endl;
    cerr << "eval : " << e->eval() << endl;
  }
}

salaam:/cm/ENSTA/POlY/EX6 $ ./tEX_2
infix   : ((((((((((1 + 1) + (1 + 1)) ...
prefix  : + + + + + + + + + + 1 1 + 1 ...
postfix : 1 1 + 1 1 + + 1 1 + 1 1 + + ...
eval : 1024
infix   : ((((((((((1 + 1) + (1 + 1)) ...
prefix  : + + + + + + + + + + 1 1 + 1 ...
postfix : 1 1 + 1 1 + + 1 1 + 1 1 + + ...
eval : 1024

allocated expressions : 2058
i 0 GC_gc_no 5 undestroyed expressions : 2056
i 1 GC_gc_no 6 undestroyed expressions : 2053
i 2 GC_gc_no 7 undestroyed expressions : 2048
i 3 GC_gc_no 8 undestroyed expressions : 2039
i 4 GC_gc_no 9 undestroyed expressions : 2022
i 5 GC_gc_no 10 undestroyed expressions : 1989
i 6 GC_gc_no 11 undestroyed expressions : 1924
i 7 GC_gc_no 12 undestroyed expressions : 1795
i 8 GC_gc_no 13 undestroyed expressions : 1538
i 9 GC_gc_no 14 undestroyed expressions : 1025
i 10 GC_gc_no 15 undestroyed expressions : 0
salaam:/cm/ENSTA/POlY/EX6 $
 

Programmation générique

Bibliographie

• The C++ Programming Language

by Bjarne Stroustrup
Paperback - 910 pages 3rd edition (July 1997)
Addison-Wesley Pub Co; ISBN: 0201889544
 
La référence indispensable. Existe en Français.
• Effective C++ : 50 Specific Ways to Improve Your Programs and Designs

by Scott Meyers
Paperback - 256 pages 2nd edition (September 1997)
Addison-Wesley Pub Co; ISBN: 0201924889
 
Un traitement en profondeur de diverses techniques et idiomes. Chaudement recommandé. Existe en Français.
• More Effective C++ : 35 New Ways to Improve Your Programs and Designs

by Scott Meyers
Paperback - 318 pages (December 1995)
Addison-Wesley Pub Co; ISBN: 020163371X
 
La suite du précédent. Chaudement recommandé également. Existe en Français.

• The Design and Evolution of C++

by Bjarne Stroustrup
Paperback - 461 pages (April 1994)
Addison-Wesley Pub Co; ISBN: 0201543303
 
A réserver aux fanas du langage ou des processus de standardisation... Une histoire fascinante de la genèse et du processus d'élaboration du langage. Explique notamment pourquoi certaines possibilités n'ont pas été retenues.