Polymorphisme et check d'égalité

Le problème exposé dans ce sujet a été résolu.

Bonjour à tous. Un problème complexe m'amène à vous pour me conseiller. Je possède des classes qui héritent l'une de l'autre. Appelons les A, B (qui hérite de A) et C (qui hérite de B). Chacune de ces classes possède une valeur interne (dans mon exemple, ce sera un int). Lorsque je possède deux pointeurs de type A* j'aimerais pouvoir comparer mes deux objets : je voudrais pouvoir dire qu'il sont égaux si et seulement si ils sont du même type et si leurs valeurs internes sont les mêmes. Je veux faire ce test au travers d'une fonction match, de façon à pouvoir écrire, par exemple :

1
2
3
A* x = new B;
A* y = new C;
if(x->match(y)) { /*...*/ }

Je vois deux solutions pour faire cela, mais aucune des deux ne me satisfait complètement.

Solution 1 : test de type et dynamic_cast

Pour cette première solution, ma fonction match est virtuelle. Elle compare le type local avec le type du paramètre. Si les types ne correspondent pas, c'est immédiatement faux. Si les types correspondent, un dynamic_cast est effectué pour pouvoir ensuite comparer les éléments. (voir code ci-dessous). C'est une solution assez simple et qui semble faire son job. Mais ma grand-mère m'a toujours appris à me méfier des dynamic_cast, c'est le Mal !

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <typeinfo>

/*** CLASS A ***/

class A
{
    public:
                       A(int a_);
                       A(const A& x);
        virtual        ~A();
        virtual A*     clone() const;

        virtual bool   match(const A* x) const;

    private:
        int            a;
};

A::A(int a_) :
    a(a_)
{
    std::cout << "A::A(int)" << std::endl;
}

A::A(const A& x) :
    a(x.a)
{
    std::cout << "A::A(const A&)" << std::endl;
}

A::~A()
{
    std::cout << "A::~A()" << std::endl;
}

A* A::clone() const
{
    std::cout << "A::clone() const" << std::endl;
    return new A(*this);
}

bool A::match(const A* x) const
{
    std::cout << "A::match(const A*)" << std::endl;
    std::cout << "typeid(*this).name() = " << typeid(*this).name() << std::endl;
    std::cout << "typeid(*x).name() = " << typeid(*x).name() << std::endl;
    if(typeid(*this) != typeid(*x))
        return false;
    return (this->a == x->a);
}


/*** CLASS B ***/

class B : public A
{
    public:
                       B(int a_, int b_);
                       B(const B& x);
        virtual        ~B();
        virtual A*     clone() const;

        virtual bool   match(const A* x) const;

    private:
        int            b;
};

B::B(int a_, int b_) :
    A(a_),
    b(b_)
{
    std::cout << "B::B(int,int)" << std::endl;
}

B::B(const B& x) :
    A(x),
    b(x.b)
{
    std::cout << "B::B(const B&)" << std::endl;
}

B::~B()
{
    std::cout << "B::~B()" << std::endl;
}

A* B::clone() const
{
    std::cout << "B::clone() const" << std::endl;
    return new B(*this);
}

bool B::match(const A* x) const
{
    std::cout << "B::match(const A*)" << std::endl;
    if(!this->A::match(x))
        return false;
    std::cout << "dynamic_cast<const B*>" << std::endl;
    const B* xx = dynamic_cast<const B*>(x);
    return this->b == xx->b;
}


/*** CLASS C ***/

class C : public B
{
    public:
                       C(int a_, int b_, int c_);
                       C(const C& x);
        virtual        ~C();
        virtual A*     clone() const;

        virtual bool   match(const A* x) const;

    private:
        int            c;
};

C::C(int a_, int b_, int c_) :
    B(a_, b_),
    c(c_)
{
    std::cout << "C::C(int,int,int)" << std::endl;
}

C::C(const C& x) :
    B(x),
    c(x.c)
{
    std::cout << "C::C(const C&)" << std::endl;
}

C::~C()
{
    std::cout << "C::~C()" << std::endl;
}

A* C::clone() const
{
    std::cout << "C::clone() const" << std::endl;
    return new C(*this);
}

bool C::match(const A* x) const
{
    std::cout << "C::match(const A*)" << std::endl;
    if(!this->B::match(x))
        return false;
    std::cout << "dynamic_cast<const C*>" << std::endl;
    const C* xx = dynamic_cast<const C*>(x);
    return this->c == xx->c;
}

Solution 2 : utiliser un genre de visiteur

Pour cette solution, chacune des classes a connaissance de l'existence des autres et implémente 3 fonctions supplémentaires crossMatchA, crossMatchB et crossMatchC. Mais je n'aime pas trop l'idée que chaque classe connaisse l'existence des autres.

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <iostream>
#include <typeinfo>

class A;
class B;
class C;

/*** CLASS A ***/

class A
{
    public:
                       A(int a_);
                       A(const A& x);
        virtual        ~A();
        virtual A*     clone() const;

        virtual bool   match(const A* x) const;

        virtual bool   crossMatchA(const A* x) const;
        virtual bool   crossMatchB(const B* x) const;
        virtual bool   crossMatchC(const C* x) const;

    private:
        int            a;
};

A::A(int a_) :
    a(a_)
{
    std::cout << "A::A(int)" << std::endl;
}

A::A(const A& x) :
    a(x.a)
{
    std::cout << "A::A(const A&)" << std::endl;
}

A::~A()
{
    std::cout << "A::~A()" << std::endl;
}

A* A::clone() const
{
    std::cout << "A::clone() const" << std::endl;
    return new A(*this);
}

bool A::match(const A* x) const
{
    std::cout << "A::match(const A*)" << std::endl;
    return x->crossMatchA(this);
}

bool A::crossMatchA(const A* x) const
{
    std::cout << "A::crossMatchA(const A*)" << std::endl;
    return (this->a == x->a);
}

bool A::crossMatchB(const B* x) const
{
    std::cout << "A::crossMatchB(const B*)" << std::endl;
    return false;
}

bool A::crossMatchC(const C* x) const
{
    std::cout << "A::crossMatchC(const C*)" << std::endl;
    return false;
}


/*** CLASS B ***/

class B : public A
{
    public:
                       B(int a_, int b_);
                       B(const B& x);
        virtual        ~B();
        virtual A*     clone() const;

        virtual bool   match(const A* x) const;

        virtual bool   crossMatchA(const A* x) const;
        virtual bool   crossMatchB(const B* x) const;
        virtual bool   crossMatchC(const C* x) const;

    private:
        int            b;
};

B::B(int a_, int b_) :
    A(a_),
    b(b_)
{
    std::cout << "B::B(int,int)" << std::endl;
}

B::B(const B& x) :
    A(x),
    b(x.b)
{
    std::cout << "B::B(const B&)" << std::endl;
}

B::~B()
{
    std::cout << "B::~B()" << std::endl;
}

A* B::clone() const
{
    std::cout << "B::clone() const" << std::endl;
    return new B(*this);
}

bool B::match(const A* x) const
{
    std::cout << "B::match(const A*)" << std::endl;
    return x->crossMatchB(this);
}

bool B::crossMatchA(const A* x) const
{
    std::cout << "B::crossMatchA(const A*)" << std::endl;
    return false;
}

bool B::crossMatchB(const B* x) const
{
    std::cout << "B::crossMatchB(const B*)" << std::endl;
    return this->A::crossMatchA(x) && (this->b == x->b);
}

bool B::crossMatchC(const C* x) const
{
    std::cout << "B::crossMatchC(const C*)" << std::endl;
    return false;
}


/*** CLASS C ***/

class C : public B
{
    public:
                       C(int a_, int b_, int c_);
                       C(const C& x);
        virtual        ~C();
        virtual A*     clone() const;

        virtual bool   match(const A* x) const;

        virtual bool   crossMatchA(const A* x) const;
        virtual bool   crossMatchB(const B* x) const;
        virtual bool   crossMatchC(const C* x) const;

    private:
        int            c;
};

C::C(int a_, int b_, int c_) :
    B(a_, b_),
    c(c_)
{
    std::cout << "C::C(int,int,int)" << std::endl;
}

C::C(const C& x) :
    B(x),
    c(x.c)
{
    std::cout << "C::C(const C&)" << std::endl;
}

C::~C()
{
    std::cout << "C::~C()" << std::endl;
}

A* C::clone() const
{
    std::cout << "C::clone() const" << std::endl;
    return new C(*this);
}

bool C::match(const A* x) const
{
    std::cout << "C::match(const A*)" << std::endl;
    return x->crossMatchC(this);
}

bool C::crossMatchA(const A* x) const
{
    std::cout << "C::crossMatchA(const A*)" << std::endl;
    return false;
}

bool C::crossMatchB(const B* x) const
{
    std::cout << "C::crossMatchB(const B*)" << std::endl;
    return false;
}

bool C::crossMatchC(const C* x) const
{
    std::cout << "C::crossMatchC(const C*)" << std::endl;
    return this->B::crossMatchB(x) && (this->c == x->c);
}

Qu'en pensez-vous ? Une meilleure solution à proposer ?

Merci d'avance, Caduchon.

+0 -0

Lu'!

Etrange comme problème. Une possibilité que je vois est d'ajouter une fonction privée (et virtuelle) d'évaluation à A et de supprimer le point de variation sur match en comparant this->eval() et other->eval().

Le retour d'eval pourrait alors être std::pair<hash_code d'un type, encoding du contenu d'un objet>.

Cette solution n'est pas très élégante mais demande peut être un poil moins de code.

+0 -0

Oui, c'était une troisième hypothèse. Je pourrais faire une fonction virtuelle qui renvoie un hash (le plus rapide possible) avec éventuellement un risque de collision. Mais le problème, c'est que dans le cadre de mon application, ça va matcher presque tout le temps. Donc ça ne peut pas être couteux de matcher…

+0 -0

Le hash code du type est fournit par le standard : http://www.cplusplus.com/reference/typeinfo/type_info/hash_code/ Après, je ne sais pas comment c'est fait derrière (puis c'est implementation defined), mais j'ose espérer que ça n'explose pas par rapport à un simple typeid.

Pour l'encoding de l'objet … Effectivement le surcoût peut être désagréable. Mais je vois pas trop d'autre manière de faire ça. Peut être que d'autres seront plus inspirés.

+0 -0

Ca sent l'erreur de conception ça. En général, on ne se pose pas ce type de problème en C++. On part du principe que polymorphisme et valeur sont incompatibles. Et donc, polymorphisme et test d'égalité n'ont aucun sens ensemble.

En Java, ils se posent très souvent la question à cause de l'absence de polymorphisme paramétrique statique et du fait que du coup, les conteneurs sont des conteneurs de God Objects. Et du coup, ils ont de la littérature sur comment implémenter correctement la méthode equals().

Bref, c'est quoi ton vrai problème ? Quel est le sens de cette fonction qui compare une partie de l'état de deux entités distinctes et qui exige que ces entités soient de même type ?

PS: La solution Visiteur est effectivement un moyen de gérer le double-dispatch. On le voit régulièrement pour gérer les collisions. Un hash/id constexpr associé à chaque classe est effectivement une solution … dans la lignée du typeid() (car il n'y a aucune différence hormis l'emploi d'huile de coude)

+5 -0

Je t'avoue ne pas vraiment comprendre pourquoi ca va si loin, ou alors c'est moi qui me trompe ^^

Ta methode match ne devrait pas avoir à être virtuelle ! Un simple :

1
2
3
4
5
6
bool A::match(A* toto){
    if(this->getType() == toto.getType())
        if(this->getValue() == toto.getValue())
            return true;
    return false;
}

Ensuite ton getType renvoie un entier ou une enumération (par exemple) et ton getValue renvoie la valeur.

Ce qui me ferais comme prototypes :

1
2
3
virtual Type A::getType();
int A::getValue();
bool A::match(A*);

J'ai peut être fait fausse route mais bon, au moins j'apprendrais ! :D

+0 -0

Merci pour vos réponses. Désolé pour ma réponse tardive.

La solution de Ricocotam n'est pas idiote, il faudrait affiner un peu car chaque classe possède des valeurs, il faut donc comparer dans les classes parentes également.

Pour préciser le problème. Il ne s'agit pas vraiment d'une sémantique de valeur, j'ai justement écarté cette notion dans mon architecture de la façon suivante.

Ma classe mère est une classe Variable qui décrit une variable sans contenir sa valeur. En l'occurrence elle possède seulement un nom :

1
2
3
4
5
6
class Variable
{
  /* ... */
  protected:
    std::string name;
};

De là, héritent deux classes, Input et Output qui sont à nouveau des squelettes décrivant des variables, dont les finalités sont différentes. Les variables de type input ont la particularité de posséder une valeur de référence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Input : public Variable
{
  /* ... */
  protected:
    double ref;
};
class Ouptut : public Variable
{
  /* ... */
};

De la classe Input, héritent des nouvelles classes de types spécifiques, par exemple BoundedReal ou Set. La première borne les valeurs possibles, la deuxième ne propose qu'une liste de valeurs possibles.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class BoundedReal : public Input
{
  /* ... */
  protected:
    double lowerBound;
    double upperBound;
};
class Set : public Input
{
  /* ... */
  protected:
    std::set<double> allowedValues;
};

Sur base de ces classes élémentaires représentant des squelettes de variables, je crée une classe Element qui est un squelette d'ensemble de variables :

1
2
3
4
5
6
7
class Element
{
  /* ... */
  private:
    std::vector<Input*> inputs;
    std::vector<Ouptut*> outputs;
};

La finalité est d'avoir une classe à sémantique de valeur, par exemple Value, qui se réfère à un Element comme squelette, et possède des valeurs associées aux variables décrites dans Element.

1
2
3
4
5
6
7
8
class Value
{
  /* ... */
  private:
    boost::shared_ptr<Element> element;
    std::vector<double> inputValues;
    std::vector<double> outputValues;
};

L'objectif, et la source de mon problème, est de pouvoir s'assurer que deux instances de la classe Value utilisent bien le même Element avant de les utiliser entre elles. En particulier, je veux pouvoir construire des collections de Value en m'assurant qu'elles ont bien toutes le même Element comme référence.

Une premières vérification se fait en regardant le pointeur lui-même. Si le pointeur vers l'Element est identique, c'est bon. Mais je souhaite pouvoir comparer deux Element pour m'assurer qu'ils sont identiques, même s'il sont des instances différentes. Je dois donc vérifier que toutes les variables contenues dans l'Element ont toutes les mêmes caractéristiques.

+0 -0

Pour moi tu as juste à faire un comparateur (operator==) pour input et output, après à toi de trouver comment faire tes comparaisons… Mais la comparaison doit pouvoir être fait le plus haut possible donc je pense qu'il faut que tu détermine au niveau de output et de input l'opérateur == (puisque tu veux comparer deux éléments qui sont composé de tableaux de Input et Output)

+0 -0

Du coup pas vraiment. Je vois plein de difficultés : le fait que les vecteurs ne sont pas forcément dans le même ordre => O(N²) pour les matchings.

A la limite, je pensais vaguement à une lightweight factory. L'idée est de ne jamais créer deux séries d'Input et Outputs qui soient identiques. Ainsi, le seul test possible est sur l'identité de l'Element (pointeur égal ou pas). Maintenant, je ne sais pas si la chose serait simple à mettre en œuvre ou pas.

+0 -0

Non seulement ce ne serait pas simple, mais en plus ce serait contraignant. L'utilisateur doit pouvoir regrouper des éléments construits de façon indépendantes mais qui s'avèrent être identiques.

J'ai fais quelques recherches supplémentaires, je suis tombé sur ceci : http://stackoverflow.com/questions/11332075/comparing-polymorphic-base-types-in-c-without-rtti

Je pense appliquer la solution de wolfgang, à savoir utiliser des static_cast à la place des dynamic_cast dans ma solution 1, qui est sans risque après comparaison du type.

+0 -0

Justement, il ne faut pas permettre à l'utilisateur de créer un nouvel objet de référence sans passer par la lightweight factory. Elle se chargera de vérifier s'il y a déjà quelque chose de référencé avec les paramètres donnés. Si oui, elle renvoie ce quelque chose, sinon elle en crée alors seulement un nouveau.

Le mérite sera de limiter les comparaisons au moment de la création de nouveaux objets.

+1 -0

Hum… c'est vrai que ce n'est pas une mauvaise idée. D'autant que j'ai déjà une factory pour construire mes éléments plus facilement et sans laisser trop de libertés à l'utilisateur.

Quelle serait la meilleure façon de stocker l'information ? Un conteneur de shared_ptr vers tout ce qui a déjà été généré ?

+0 -0

Ton conteneur est l'unique responsable. Ce peut aussi être un boost::ptr_vector<Input> ou un std::vector<unique_ptr<Input>>, et les vecteurs d'inputs peuvent être des std::vector<undeletable_ptr<Input>> (ou juste des pointeurs bruts qu'il ne faut en aucun cas effacer).
Ca sera plus performant que des shared_ptr<> et autres mélanges avec des weak_ptr<>.

Après, cela en lève en rien ta problématique de comparaison. Elle est juste déplacée. A la limite, tu peux t'amuser à tout trier par type (=> explosion du nombre de vecteurs dans la factory), ce qui lève définitivement le besoin de RTTI (qu'il soit standard ou à l'huile de coude).

+1 -0

Dans mon cas ce n'est vraiment pas un problème. Il y a peu d'éléments différents. En pratique souvent un seul. Par contre il est crucial dans mon appli de m'assurer que je travaille bien avec des objets de la même famille.

Ta solution est donc parfaite, car elle déplace le problème là où les performances ne sont vraiment pas un problème.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte