Discussion :

[BaygonV]

Bonjour !
Je lis (et relis) le libre de Bjarne Stroutrup The C++ programming language 4th Edition et j'ai un sérieux problème de compréhension de la section 27.4.1 Composing Data Structures p 782.

Bjarne me dit :

Consider writing a balanced binary tree library. Since we are providing a library to be used by
many different users, we can’t build the type of the user’s (application’s) data into our tree nodes.
We have many alternatives:

Bon ça ok, c'est juste pour mettre dans le contexte.

Des trois alternatives qu'il propose ensuite, seule la première me pose problème :

Première alternative :

We could put the user’s data in a derived class and access it using virtual functions. But (...) our interface to the user’s data is not expressed in terms of the user’s type, so we still need to use casts to access it.

Ce que j'ai compris en première lecture c'est qu'il faisait référence à quelque chose du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
class Node {
Node* fils_droit, *fils_gauche;
Data* val;
public :
Data* getVal(){ return val;}
};

En demandant à l'utilisateur de faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
class Val_double : public Data {
double val;
}

Mais alors ce serait à l'utilisateur de faire des cast et de toutes façons il me semble que c'est en fait la troisième alternative que propose Bjarne :

We could put a Data∗ into our nodes, where Data is a ‘‘universal base class’’ for our data structures. That would solve the type-checking problem(...)

Du coup j'ai imaginé qu'il voulait dire quelque chose du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
class Node{
Node* fils_gauche;
Node* fils_droit;
public : 
Node();
//Code Mystèrieux  pour moi comprenant
// Des méthodes virtuelles pour accéder à la 'valeur' du nœud mais   
// Je ne vois pas du tout comment ici sans connaitre le type de la valeur du nœud
// même en castant (vers quoi ??)
};

Et que l'on demanderait à l'utilisateur de faire quelque chose du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
class Tree_double : public Node{
double val;
//.....
};

Pour palier à mon problème de code mystère, j'ai donc imaginé qu'on ferait plutôt quelque chose du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
template <typename T> class Node{
Node* fils_gauche;
Node* fils_droit;
public : 
Node();
virtual T getVal() const = 0;
};

Et l'utilisateur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
class Tree_double : public Node<double> {
double val;
public : 
double getVal() const {return val;}
};

Mais alors, je ne vois plus du tout à quel cast mon ami Bjarne fait référence...
Bref : je suis paumé.

P.S. : J'ai d'autres problèmes dans la même section mais j'y viendrai après sinon mon post risque de faire 10 pages.

[bacelar]

On n'a pas forcement le bouquin sous le coude.
Pouvez-vous être plus explicite pour ceux qui n'ont pas le bouquin ?

[LandReagan]

Stroustrup said:

Consider writing a balanced binary tree library. Since we are providing a library to be used by
many different users, we can’t build the type of the user’s (application’s) data into our tree nodes.
We hav e many alternatives:
• We could put the user’s data in a derived class and access it using virtual functions. But the
virtual function calls (or equivalently, run-time resolved and checked solutions) are relatively
expensive, and our interface to the user’s data is not expressed in terms of the user’s
type, so we still need to use casts to access it.
• We could put a void∗ in our nodes and let the user use that to refer to data allocated outside
our nodes. But that could double the number of allocations, add many (potentially expensive)
pointer dereferences, and add the space overhead of a pointer in each node. We would
also need to use a cast to access our user data using its correct type. That cast can’t be type
checked.
• We could put a Data∗ into our nodes, where Data is a ‘‘universal base class’’ for our data
structures. That would solve the type-checking problem, but that combines the cost and
inconvenience of the previous two approaches.

C'est une introduction à la notion de Template. En relisant ces trois solutions imparfaites au problème, qui va être résolu dans les pages suivantes grâce à la programmation générique, je pense qu'il veut dire qu'on peut développer un arbre binaire pour un type donné, et qu'on peut l'adapter à d'autres types grâce à des classes dérivées qui vont en redéfinir les méthodes et dont l'accès à l'attribut se fera par un cast. D'où les méthodes virtuelles dans la classe parent, car elles devront être redéfinies dans chaque classe dérivée.

...

OK, c'est pas beaucoup plus clair si on n'a pas compris. Code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
class NoeudInt
{
   NoeudSuivant* ns;
   NoeudPrecedent* np;
public:
   int* valeur;
   virtual bool compare(int x) const {return *valeur < x;} // juste un exemple de méthode
}

On définit donc notre noeud d'arbre binaire pour stocker des entiers. Maintenant, si on veut stocker des doubles:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
class NoeudDouble : public NoeudInt
{
public:
   bool compare(double x) const {return (double)(*valeur) < x;}
}

... après avoir changé le pointeur valeur pour un pointeur sur double:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
NoeudDouble nd;
double valeurLocale(1.3654);
double* pValeurLocale = &valeurLocale;
nd.valeur = (int*)pValeurLocale;

Je ne l'ai pas compilé. Ça me semble tellement foireux...

Ce serait la première solution. La deuxième est obtenue en remplaçant "int* valeur" par "void* valeur". Ça revient au même, à part qu'on comprend mieux qu'il faudra caster cette valeur. La troisième par Data*, type à définir et caster pour l'utilisation.

Dans chacun des trois cas, Stroustrup reproche le cast (qui détruit un des avantages du C++, le typage fort) et l'utilisation des fonctions virtuelles, relativement gourmandes en ressource.

[koala01]

Salut,

Si c'est pour introduire à l'utilisation des template, il n'y a pas grand chose à dire d'autre que "on a plusieurs possibilités, mais aucune de celles-ci ne seront réellement utilisable pour différentes raisons".

C'est, en gros, ce qu'il te dit :

1. Nous pouvons avoir une classe de base Data que l'on spécialise à chaque fois pour chaque type de donnée... Mais cela nécessite des transtypage à n'en plus finir
2. l'utilisation d'un pointeur sur void est crade
3. Nous pourrions avoir un "AbstractNode" qui servirait de classe de base à tous les noeuds, spécialisés à chaque fois pour représenter un type de donnée spécifique, mais cela combine les mauvais cotés des solutions 1) et 2)

D'une certaine manière, le simple fait que tu te dise "ca parrait tellement zarbi" en essayant de mettre ces solutions en oeuvre démontre qu'il a gagné son pari : il t'a fait comprendre qu'il faut "une autre solution, qui ne soit pas tiré du paradigme orienté objet", et tu es tout à fait d'accord avec lui.

Fin de l'histoire, la messe est dite : le paradigme orienté objet apporte beaucoup de solutions mais n'est -- décidément -- pas la solution ultime à tous les problèmes