Ubuntu-fr

Mikkou

Problème en C++ avec les templates et l'héritage

Bonjour à tous,

Je suis actuellement en train d'écrire une bibliothèque pour le Data Mining.
À la base je viens du monde Java et après quelques tests de performance et de consommation mémoire j'ai décidé de me tourner vers le C++ qui semble bien plus efficace pour ce type d'application. J'apprends le C++ sur le tas et je pense avoir plutôt bien pigé les concepts qui sont quand même assez proche de Java mais avec énormement de petites subtilités.
Cette bibliothèque s'appuie énormément sur l'utilisation de templates avec définitions de conteneurs, structures de données et algorithmes génériques.

Mais j'ai un pseudo problème (c'est pas vraiment bloquant) que je ne comprends pas trop et je vais essayer d'être le plus clair possible. Je n'ai bizarrement pas trouvé de solution pour ce problème qui je pense est plutôt courant.
1 - J'ai défini un conteneur template List<A> qui est tout simplement un héritage de vector<A> mais avec encapsulation de méthodes ensemblistes qui me sont bien utiles (union, intersection, ...)
2 - J'ai une structure de données Sequence<B> qui est un conteneur dont les élèments sont ordonnés (surcharges des opérateurs de comparaisons obligatoire pour l'élément de type B) et qui encapsule aussi les opérations ensemblistes.
3 -  Une structure de données ContextualSequence<B> qui hérite de Sequence<B> et d'une interface IContextualFeature qui lui donne un comportement bien particulier (rentrer dans les détails serait trop long).
4 - J'ai un algorithme template MatrixBuilder::similarityMatrix<C>(List<C>, Metric<C>) qui prend en paramètre une List<C> et une métrique Metric<C> et retourne une matrice Matrix<C,C,float>. Concrètement, cet algorithme calcule une matrice de similarité entre tous les élèments de List<C> et a donc besoin d'une métrique (une mesure de distance/similarité) entre deux éléments C.
En gros cet algorithme utilise un design pattern 'Strategy' qui permet d'exterioriser une partie de code d'un algorithme (e.g. le Collection.sort() en Java) et de pouvoir le changer à la volée.
5 - J'ai définie une méthode de calcul de similarité (i.e. métrique) entre deux séquences d'itemsets (i.e. Sequence<Set<B>*>) et qui s'appelle DTWSI<B> dans l'objectif d'utiliser MatrixBuilder::similarityMatrix.

Problème:
Tout fonctionne très bien si j'envoie en paramètre une List<Sequence<Set<B>*>*> et la métrique DTWSI<B>.
Par contre le compilo me gueule dessus si j'envoie en paramètre une List<ContextualSequence<Set<B>*>*> avec DTWSI<B> et me dit qu'il attend des 'Sequence' et pas des 'ContextualSequence' alors que les 'ContextualSequence' sont des 'Sequence' par héritage, donc je comprend pas trop.
Voici le code qui ne compile pas:

typedef ContextualSequence< Set< unsigned char >*> DataSeq;
typedef Sequence< Set< unsigned char >*> Seq;

int main(int argc, char **argv) {
    
    List< DataSeq* >* listSequence =    
        &SequenceBuilder::loadFromDnaMicroArrays("Dataset/Breast_Cancer:50_1-3.csv");
    
    DTWSI<unsigned char> metric;
    Matrix< Seq,Seq,float>* matrix = 
        &MatrixBuiler::similarityMatrix< Seq >(*listSequence,metric);
    
    cout << *matrix << endl;

        delete listSequence;
        delete matrix;
}

Si je veux que cela compile je dois créér une nouvelle liste de type List<Sequence<Set<B>*>*> dans laquelle j'insère les 'ContextualSequence' de la première liste. Alors même si ça ne me gène pas plus que ça, pour le moment, je trouve ça plutôt lourd et dérange mon cerveau de Javatien.
De plus ma librairie évolue très vite et cela pourrait devenir un peu plus problématique car j'ai d'autres algorithmes qui fonctionnent à des niveaux d'abstraction bien plus important.
Voici le code qui compile:

typedef ContextualSequence< Set< unsigned char >*> DataSeq;
typedef Sequence< Set< unsigned char >*> Seq;

int main(int argc, char **argv) {
    
    List< DataSeq* >* listSequence1 =    
        &SequenceBuilder::loadFromDnaMicroArrays("Dataset/Breast_Cancer:50_1-3.csv");
        
    List< Seq* >* listSequence2 = new List< Seq* >;
    
    List< DataSeq* >::const_iterator it;
    for(it = listSequence1->begin() ; it != listSequence1->end() ; ++it) {
        listSequence2->push_back(*it);
    }
    
    DTWSI<unsigned char> metric;
    Matrix< Seq,Seq,float>* matrix = 
        &MatrixBuiler::similarityMatrix< Seq >(*listSequence2,metric);
    
    cout << *matrix << endl;

        delete listSequence1;
        delete listSequence2;
        delete matrix;
}

Je souhaitais donc savoir s'il y a une manière élégante de gérer ce soucis sans faire tout pleins de cast et autres atrocités.

Merci bien pour votre aide,
Bonne journée,
Mikkou

Luc Hermitte

Re : Problème en C++ avec les templates et l'héritage

1- C'est une erreur
Tu ne veux pas dériver les conteneurs standards. Ce n'est pas fait pour, tu va aller de galère en galère.
De plus, tous les algos ensemblistes sont déjà dans <algorithm>. À la limite si tu trouves leur utilisation un chouilla peu pratiques, il n'est pas impossible qu'une version simplifiée se trouve dans boost.

2- std::set ?
Sinon, il est possible d'aller plus vite avec des vecteurs triés. Mais attention, en OO une liste triée n'est pas une liste.

3- Oublie le Java.
L'héritage de conteneurs est une catastrophe (slicing, collecte, non prévu pour être polymorphe, etc)

6- oh les vilains pointeurs pris sur des trucs renvoyés par valeur...

template <typename Seq_, typename Metric_>
inline
Matrix<typename Seq_::value_type, typename Seq_::value_type, double> buildSingularityMatrix(Seq_ const& seq, Metric_ const& metric) {
    Matrix<typename Seq_::value_type, typename Seq_::value_type, double> res(seq.size(), seq.size());
    for (size_t i=0 ; i!=seq.size() ; ++i) {
        for (size_t j=0 ; j!=seq.size() ; ++j) {
            res(i,j) = metric(seq[i], seq[j]); // à supposer que bati sur un vecteur, à convertir en itérateurs sinon
        }
    }
    return res;
}

PS: tu ne veux pas utiliser new pour instancier des conteneurs. Tu perds tous l'avantage RAII des conteneurs à procéder de la sorte.
PPS: les forums C++ comme celui de dvpz sont plus adaptés à traiter ce genre de questions ...

Dernière modification par Luc Hermitte (Le 22/02/2012, à 16:26)

Mikkou

Re : Problème en C++ avec les templates et l'héritage

Merci Luc pour ta réponse.
Je crois que j'ai encore beaucoup de chose à apprendre sur le C++ ...

1- C'est une erreur
Tu ne veux pas dériver les conteneurs standards. Ce n'est pas fait pour, tu va aller de galère en galère.
De plus, tous les algos ensemblistes ont déjà dans <algorithm>. À la limite si tu trouves leur utilisation un chouilla peu pratiques, il n'est pas impossible qu'une version simplifiée se trouve dans boost.

Oui on m'a fait la remarque sur un autre forum. Mais en quoi ce n'est pas fait pour ?
En fait les opérations que j'ai rajouté encapsulent les algos ensemblistes qui sont dans algorithm.
J'ai pas trouvé dans boost mais je vais les rendre externes et plus faciles à utiliser.

2- std::set ?
Sinon, il est possible d'aller plus vite avec des vecteurs triés. Mais attention, en OO une liste triée n'est pas une liste.

Hum oui justement, à l'instart de List<A>, Sequence<A> hérite de std::set.

3- Oublie le Java.
L'héritage de conteneurs est une catastrophe (slicing, collecte, non prévu pour être polymorphe, etc)

Aie ça ne m'arrange pas du tout ça, j'avais justement basé le fonctionnement de ma librairie sur ce genre de choses.
Je vais y réfléchir.

6- oh les vilains pointeurs pris sur des trucs renvoyés par valeur...

Pour les vilains pointeurs en fait le type de retour est une référence et non une valeur . Mis à part les types de bases, je n'utilise que les références.
Merci pour le code qui est très proche du mien sauf quelques trucks :
- dans la déclaration du template tu met 'typename', moi je met 'class' c'est quoi la différence ?
- je n'ai jamais trop compris l'utilisation du inline à part que ça écrit directement la fonction à chaque appel lors de la compilation sans faire de macro ? (Si je dis pas n'importe quoi)
- le ::value_type sert à quoi car je n'en avais pas

Mikkou

Re : Problème en C++ avec les templates et l'héritage

Si ça peut intéresser d'autres personnes, voici la suite de la discussion dans un topic sur le siteduzero.

Luc Hermitte

Re : Problème en C++ avec les templates et l'héritage

Je réponds aux questions qui n'ont pas été abordées sur le sdz.
- Entre class et typename, la seule différence dans les paramètres templates, c'est celle que l'on veut bien leur accorder.
Dit autrement, il n'y en a pas. Mais certaines personnes utilisent class uniquement quand il est certain que le paramètre doit être une classe et ne peut pas être un type primitif comme int p.ex.

- L'inlining est nécessaire sur les fonctions qui sont déclarées et définies dans des .h. Dans le cas des fonctions template, la définition doit impérativement  (*) être dans un .h -- et dans le cas où elles ne sont pas membres (et donc pas définies dans une classe, comme en Java) l'utilisation explicite du mot clé est requise.
(*) parfois j'ai l'impression que c'est lié à des compilos, parfois non.

- Le value_type de vector<T>, c'est T. À partir du conteneur, cela permet de retrouver le type des éléments stockés.
Là l'utilisation de typename n'a rien à voir avec celle que je décrivais dans le premier point, elle est requise, et class n'est pas utilisable à la place. Pour faire court, regarde la FAQ C++ de dvpz.