Discussion :

[BaygonV]

Bonjour, cela fait quelques semaines que j'étudie le C++ et pour le moment voici ce que j'ai compris des différents moyens qu'offre ce langage pour généraliser et particulariser des 'concepts' :

1) On peut le faire via l'héritage et le polymorphisme, ce qui permet en utilisant des pointeurs et des références de spécialiser des concepts à l’exécution.
2) On peut le faire via des instances de template (pas très sûr du vocabulaire), ce qui permet de particulariser des concepts... "a la compilation".
3) J'imagine, qu'on peut imaginer tout un tas de tricotage des deux briques de bases ci-dessus.

Justement je m'essaye de manière abstraite (je ne code pas) à imaginer comment utiliser un tel tricotage et je dois avouer que je m'y perds, à la fois par méconnaissance du langage et par manque de méthode.

A titre d'exercice, j'essaie de modéliser une classe noeud de graphe et j'en suis arrivé à imaginer quelque chose comme ça (plus facile à exprimer en terme de code mais je n'ai pas testé et ne suis meme pas sur que certaines constructions soient réellement valides, voir commentaires) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
template <typename Vtype> Node { /*class de noeud de base */
    Vtype val; //Valeur dans le Noeud
    class Linktype {
         Node<Vtype>* pointedNode;
    public :
        virtual/*?*/ Node<Vtype>* linkTo();
   };
 
   vector<Linktype*> links;
 
public : 
/* ...Vtype get() const ; ....  Constructeurs etc ...... */ 
};
 
template<typename Vtype, typename Ftype> 
class Node : public Node<Vtype> { /* classe de noeud dont les liens peuvent être flaggés
                                                     * vraiment pas sur de la validité syntaxique */
 
    template<typename Ftype> 
    class Linktype : public Node<Vtype>::Linktype { /* Toujours pas du tout sur de la validité */
        Ftype flag;
   };
   /* .... etc ..... */
};

Est ce que cette "organisation" vous semble plausible ?
Est ce que vous pouvez me diriger vers des liens méthodiques ?
J'aimerais avoir assez de méthodes pour que la partie codage soit le plus proche d'une formalité possible (toujours modulo ma connaissance du langage...).

[Trademark]

Je vois ce que tu essayes de faire mais, en dehors de toute erreur syntaxique, l'héritage est inutile ici, tu peux tout résoudre à la compilation.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class EgdeValue, class NodeValue> 
class BidirectionalEdge
{
  EdgeValue value;
  Node<NodeValue, EdgeValue> start, end;
  /* methods not shown */
};
 
template <class NodeValue, EdgeValue> 
class Node
{
  NodeValue value;
  std::vector<BidirectionalEdge<EdgeValue, NodeValue>> edges;
 
  /* methods not shown */
};
 
template <NodeValue, EdgeValue> 
using Graph = Node<NodeValue, EdgeValue>

Par rapport à ta solution initiale, ici on stocke obligatoirement des informations sur les noeuds et les arêtes. Il te manquait principalement une connaissance qui est la spécialisation template :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class NodeValue> 
class BidirectionalEdge<void, NodeValue>
{
  Node<NodeValue, void> start, end;
  /* methods not shown */
};
 
template <EdgeValue>
class Node<void, EdgeValue>
{
  std::vector<BidirectionalEdge<EdgeValue, void>> edges;
 
  /* methods not shown */
};

Avec cette technique tu peux maintenant avoir toutes les combinaisons que tu veux. Arêtes sans/avec info, noeud sans/avec info, ...

Bon les liens maintenant :
Marier l'héritage et les templates : http://alp.developpez.com/tutoriels/type-erasure/
Une autre utilisation des templates : http://loulou.developpez.com/tutoriels/cpp/metaprog/
Voir le livre "modern C++ design" par Alexandrescu pour plus d'explication sur le tuto précédent.

La faq de developpez pourra fortement t'aider sur des détails quand tu implémenteras : http://cpp.developpez.com/faq/cpp/

Tu peux aussi aller lire le design de la bibliothèque Boost.Graph : http://www.boost.org/doc/libs/1_55_0...doc/index.html
Ça risque d'être un peu compliquer par contre, mais c'est une librairie de graphe quasiment entièrement basée sur les templates (donc pas d'héritage), tu peux juste lire les descriptifs pour "voir un peu" comment ça marche.

Par contre, c'est bien de vouloir comprendre "en théorie" mais ça ne sera jamais suffisant, il faut absolument que tu codes. Commence par les exercices simples comme paramétrer une liste chainée par le type des éléments...

[BaygonV]

Merci de ta réponse.
En fait j'ai bien pensé a la spécialisation template mais sans savoir qu'on pouvait spécialiser avec un 'void' et effectivement ça me parait intéressant.
Du coup j'en profite pour poser plus de questions :

1) J'ai l'impression que 'ma' méthode permet de factoriser plus de code, est ce que j'ai tort ?

2) Dans les faits, est ce que 'ta' méthode et 'ma' méthode sont équivalentes en terme de généralisations futures ?

3) Est ce que je dois 'toujours' (disont majoritairement) préférer une méthode qui décide à la compilation à une qui décide à l'éxecution ?

4) Si les deux notions existent (template+heritage) c'est que ces méthodes ne doivent pas avoir tout a fait le même but ni les mêmes possibilités mais j'ai l'impression que l'une pourrait en fait presque toujours remplacer l'autre et la seule manière de choisir efficacement entre les deux est de pouvoir clairement distinguer ce 'presque toujours'.

Par exemple la 'simple' notion de valeur de noeud, qu'on généralise tous les deux via un paramètre de template ne pourrait-elle pas être elle aussi généralisée via héritage ?
(à priori je dirais non mais c'est plus parce que je ne vois pas du tout comment -par exemple- aller récupérer cette valeur -avec le bon type et sans conserver un paramètre Type-. Rien ne me permet de me dire que quelqu'un d'autre n'y arriverait pas.)
Si impossibilité il y a je n'arrive pas à me donner une 'raison' valable.



Bon je vais aller voir dans les différents liens que tu proposes si je trouve une réponse.

[Iradrille]

Par exemple la 'simple' notion de valeur de noeud, qu'on généralise tous les deux via un paramètre de template ne pourrait-elle pas être elle aussi généralisée via héritage ?

Si, certainement, il n'y a pas d'exemple dans la STL (il me semble), mais regardes l'implementation de digest en D : 2 implémentations, 1 orienté objet et 1 basée sur les templates.

Je trouve ton implémentation de noeud à la fois bonne et mauvaise :


Mauvaise car :
Le concept de noeud est très lié à un type de graphe précis. Par exemple un "noeud d'une liste chainée" sera différent d'un "noeud d'un arbre rouge et noir".
Et ces deux types de noeuds n'ont rien en commun. Il n'y à pas de sens à mettre un "noeud d'une liste chainée" dans un arbre rouge et noir (et inversement).
Il n'y à donc pas besoin d'avoir une interface commune pour 2 types de noeuds différents.
Le noeud est aussi un concept utile au graphe, mais l'utilisateur n'a pas besoin de savoir qu'il existe. Ca sera certainement une classe interne au Graphe

Code :

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

1
2
3
4
5
6
7
8
9
template <class T>
struct Graphe {
   struct Node {
      T value;
      Node *suivant;
   };
   // ...
   Node * root;
};

Pas d'héritage ?
L'héritage serait utile seulement si tu as besoin d'avoir un graphe avec des noeuds différents dans le même graphe. Comme ton exemple de flag sur les liens.
Imaginons que le type de flag ne soit pas connu à la compilation

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T>
struct Graphe {
   struct AbstractNode {
      T value;
      AbstractNode *next;
      virtual ~AbstractNode() = 0 { }
   };
 
   struct NoFlagNode : AbstractNode { }
 
   struct IntFlagNode : AbstractNode {
      int flag;
   };
 
   struct StringFlagNode : AbstractNode {
      std::string flag;
   };
   // ...
   AbstractNode * root;
};

Avec quelque chose du genre, au graphe, on peut ajouter des

• NoFlagNode
• IntFlagNode
• StringFlagNode

Et les templates ?
Si le type de flag est connu à la compilation, alors les templates sont la pour ça.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
struct Graphe {
   struct AbstractNode {
      T value;
      AbstractNode *next;
      virtual ~AbstractNode() = 0 { }
   };
 
   struct NoFlagNode : AbstractNode { }
 
   template <class U>
   struct FlagNode : AbstractNode {
      U flag;
   };
   // ...
   AbstractNode * root;
};

Avec quelque chose du genre, au graphe, on peut ajouter des

• NoFlagNode
• FlagNode<int>
• FlagNode<float>

Maintenant, si le graphe ne peut contenir que des noeuds identiques :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T, class U=void>
struct Graphe {
   template <class = U>
   struct Node {
      T value;
      U flag;
      Node *next;
   };
 
   template <>
   struct Node<void> {
      T value;
      Node *next;
    };
   // ...
   Node<U> *root;
};

Ça permet d'avoir un graphe contenant des noeuds avec ou sans flag (tous les mêmes !) mais tu peux déclarer différents graphe :

• Graphe<int, int> g; élément == int, flag == int
• Graphe<int> g; élément == int, pas de flag
• Graphe<std::string, float> g; élément == string, flag == float
• ...

Pourquoi ton implémentation est bonne ?
Elle présente une bonne abstraction, mais cette abstraction n'est utile que dans un cas précis (l'héritage à un coût, que peu de personnes sont prêtes à payer quand ce n'est pas justifié).

Pour que ton abstraction soit utile il faut que ces conditions soient remplies :

• Les liens entre les noeuds sont un concept important, et différents noeuds ont des liens différents
• Un graphe peut contenir des noeuds avec et sans flag
• Le type de flag peut être différent entre les noeuds, et le type est connu à la compilation

Faut-il présenter une abstraction des liens ?
Peut être, si les liens sont un concept assez important dans le type de graphe que tu utilise, et que différents type de noeuds (dans le même graphe) peuvent avoir des liens différents.


Pour conclure :
L'abstraction que tu présente est bonne mais dans certaines conditions seulement. Si ces conditions sont remplies alors ton implémentation est bonne (syntaxe mise à part). Sinon elle présente une abstraction inutile qui induit un coût inutile.

[BaygonV]

Merci pour vos réponses que je vais lire, relire et re relire.
Cependant depuis deux jours ma 'vision' de ce que peut être un graphe a pas mal évolué et je préfère clore ce fil et en recommencer un en posant les définitions plus proprement (je l'espère) -réflexe de matheux- afin de mieux vous comprendre.
Je vais éventuellement reprendre 'la bas' des citations de vos réponses d'ici, a ce sujet, je ne comprends pas vraiment comment faire pour vous citer, je vois bien la balise \[\QUOTE\]\ mais rien qui me permette de mettre le nom de la personne citée comme tu as pu le faire Iradrille. J'attends que quelqu'un me réponde à ce sujet et je marquerai ce fil comme résolu.
Par contre, je n'attends pas pour en démarrer un nouveau, son titre : Aide au design d'une classe Graph souple et extensible.

[Flob90]

Bonjour,

4) Si les deux notions existent (template+heritage) c'est que ces méthodes ne doivent pas avoir tout a fait le même but ni les mêmes possibilités mais j'ai l'impression que l'une pourrait en fait presque toujours remplacer l'autre et la seule manière de choisir efficacement entre les deux est de pouvoir clairement distinguer ce 'presque toujours'.

A mon avis tu as répondu tout seul à cette remarque dans ton premier message : l'un est résolu à la compilation l'autre à l’exécution.

Je ne pense pas qu'il y est besoin d'aller chercher plus compliqué, la question est "est ce que le point de variation que je veux introduire est déterminé à la compilation ou à l’exécution ?" dans le premier cas la solution est une surcharge / spécialisation (selon la situation exacte), dans le second une solution technique offrant une sélection à la compilation (héritage et redéfinition dans les cas les plus usuels).

De manière plus concrète, si je cherche à écrire un service "foo" agissant sur un seul objet, je dois me demander si je sais à la compilation comment doit agir ce service, ou dit autrement si je connais le type de l'objet à la compilation (un seul point de variation). Si c'est le cas alors quelque chose comme :

Code :

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

1
2
3
4
 
template<class T>
void foo(const T&)
{ /*default stuff*/ }

devrait convenir, et dans ce cas je peux faire varier mon comportement en surchargeant au besoin :

Code :

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

1
2
3
4
 
template<class T>
void foo(const template_class<T>&)
{ /*stuff for template_class*/ }

Une petite remarque, je surcharge puisque je peux, si ce qui varie est une classe tout entière, une spécialisation de la classe convient très bien. Dans le cas contraire, alors quelque chose comme :

Code :

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

1
2
3
4
5
6
 
struct base
{
  virtual void foo()
  { /*default stuff*/ }
};

devrait convenir, et dans ce cas je peux faire varier mon comportement en redéfinissant au besoin :

Code :

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

1
2
3
4
5
6
7
 
template<class T>
struct template_class : base
{
  void foo()
  { /*stuff for template_class*/ }
};

Une remarque sur cette situation : c'est intrusif, et ça se complexifie fortement si le comportement doit changeant selon les types de deux objets (ou plus, plusieurs points de variation), voir les articles à ce sujet (mot clé : multiple dispatch), alors que cela reste "simple" si ils sont déterminés à la compilation. Mais heureusement boost vient nous offrir des solutions clés en main.

Toute la problématique est alors de bien choisir ses points de variation et de réussir à répondre à cette question pour chacun d'eux, ce qui n'est pas trivial dans toutes les situations.

[Iradrille]

Pour les citations (pas sur que ce soit la meilleure méthode, mais ça marche).

Clique sur "répondre avec citation" sur le post à citer, garde seulement ce que tu veux citer, copies tout ça quelque part (genre notepad).
Recommence autant de fois que nécessaire pour avoir toutes les citations que tu veux dans ton message.

[BaygonV]

Merci Flob90, mais qu'en est-il si je ne sais pas... je veux dire si je ne suis pas forcément l'utilisateur du service ?
Ok Iradrille !
Je ferme ce fil. Le nouveau est Aide au design d'une classe Graph souple et extensible