Discussion :

[ImmoTPA]

Bonsoir désolé de vous déranger mais il y a plusieurs points qui me chagrinent concernant les notions d'héritage et de classes templates.

J'essaie d'implémenter trois classes, la première Heap est censée être abstraite et donc non-instanciable si je ne dis pas de bêtises. La seconde et la troisième héritent de la première.

Pour l'instant je n'ai codé que les 2 premières classes, voici le code puis viendront les questions :

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
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
#ifndef HEAP_T
#define HEAP_T
 
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility> // swap
#include <algorithm> // min
#include <cmath> // log2
 
template <typename Tkey>
class Heap {
 
protected:
    typedef unsigned int node;
    typedef std::vector<Tkey> elements;
 
public:
    Heap(void);
 
    void display(void);
    void insert(const Tkey key);
    Tkey pop(void);
    void delete_element(const Tkey key);
 
    static Heap heapify(const elements& vector);     
 
protected:
    void bubble_up(const node n);            
 
    virtual node bubble_down(const node n) = 0;          // need to be specialized (Min or Max Heap ? )
    virtual void percolate_up(const node n_start) = 0;   
    virtual void percolate_down(const node n_start) = 0; 
 
protected:
    node left_son(node n) const { return n<<1; }
    node right_son(node n) const { return (n<<1) + 1; } ;
    node daddy(node n) const { return n>>1; }
    elements get_elements(void) const { return elements_; }
    size_t h_size() const { return elements_.size(); }           // also counts the fake element, might be better not to ? 
 
protected:
    elements elements_;
};
 
template <typename Tkey>
Heap<Tkey>::Heap(void){
    elements_.push_back(0);
}
 
template <typename Tkey>
void Heap<Tkey>::display(void){
    for(size_t i = 1u; i < this->h_size(); ++i)
        std::cout << elements_[i];
}
 
template <typename Tkey>
Heap<Tkey> Heap<Tkey>::heapify(const elements& vector){
 
    Heap<Tkey> heap = Heap();
 
    for(size_t i = 0; i < vector.size(); ++i)
        heap.get_elements().push_back(vector[i]);
 
    unsigned int depth = log2(vector.size()-1);  // computes the depth of the heap
 
    node starting_node(0);
 
    for(size_t k = 0; k < depth; ++k)            // computes the starting node which is the last node of the (depth-1)-level
        starting_node += pow(2.0, k);
 
    for(size_t j = starting_node; j > 0; --j)    // percolate at each down starting at the level depth-1, processing nodes from right to left
        heap.percolate_down(j);
 
    return heap;
}
 
template <typename Tkey>
void Heap<Tkey>::bubble_up(const node n){
    std::swap(elements_[n], elements_[daddy(n)]);
}
 
template <typename Tkey>
void Heap<Tkey>::insert(const Tkey key){
    elements_.push_back(key);                            // adds at the first possible position
    this->percolate_up(this->h_size()-1);         // restores invariant if needed
}
 
template <typename Tkey>
Tkey Heap<Tkey>::pop(void){
 
    if(this->h_size() <= 1){
            std::cerr << "This heap is empty, you cannot get pop any value" << std::endl;
            return Tkey();
        }
 
    Tkey returned_key = elements_[1];                   // binary heap -> min key value is at the root
    std::swap(elements_[1], elements_.back());           // swap min value key and last element
    elements_.pop_back();                              // delete last node
    this->percolate_down(1);                      // restores invariant if needed
    return returned_key;
}
 
template <typename Tkey>
void Heap<Tkey>::delete_element(const Tkey key){
    Tkey returned_key;
    for(size_t i = 1u; i < this->h_size(); ++i){
        if(elements_[i] == key){                              // need to implement operator= for Tkey
            returned_key = elements_[i];
            std::swap(elements_[this->h_size()-1], elements_[i]);
            elements_.pop_back();
            percolate_down(i);
            return returned_key;
        }
    }
    return Tkey();
}
 
#endif

et MinHeap

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
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
#ifndef MIN_HEAP
#define MIN_HEAP
 
#include "heap.hpp"
 
typedef unsigned int node;
 
 
template <typename Tkey>
class MinHeap : public Heap<Tkey>{
 
typedef std::vector<Tkey> elements;
 
public:
    node bubble_down(const node n);
    virtual void percolate_up(const node n_start);  
    virtual void percolate_down(const node n_start);
};
 
template <typename Tkey>
node MinHeap<Tkey>::bubble_down(const node n){
    if(this->right_son(n) < this->h_size()){
        node min_child = (this->elements_[this->left_son(n)] < this->elements_[this->right_son(n)]) ? this->left_son(n) : this->right_son(n);  // we swap with the min child
        std::swap(this->elements_[n], this->elements_[min_child]);
        return min_child;
    }
    else{
        std::swap(this->elements_[n], this->elements_[this->left_son(n)]);
        return this->left_son(n);
    }
}
 
template <typename Tkey>
void MinHeap<Tkey>::percolate_up(const node n_start){
    node current_node(n_start);
    while(current_node != 1 && this->elements_[current_node] < this->elements_[this->daddy(current_node)]){     // if we haven't reached the root 
                                                                                                        // and we have to swap with daddy 
        this->bubble_up(current_node);
        current_node = this->daddy(current_node);
    }    
}
 
template <typename Tkey>
void MinHeap<Tkey>::percolate_down(const node n_start){
    node current_node(n_start);
    bool have_to_swap;                               // to determine if a bubble_down operation is needed
 
    do {                                                                    // since behavior is undefined when we check outside the bounds of a vector
                                                                            // we check how many sons actually exist
        if(this->left_son(current_node) < this->h_size()){                               // at least one son
 
                if(this->right_son(current_node) < this->h_size())                        // two sons
                        // we swap if our key is greater than one of our son's
                        have_to_swap = this->elements_[current_node] > this->elements_[this->left_son(current_node)] or this->ele[current_node] > this->elements_[Heap<Tkey>::right_son(current_node)];
                else                                                            // one son
                    have_to_swap = this->elements_[current_node] > this->elements_[this->left_son(current_node)];
 
        }
        else 
            have_to_swap = false;      // no sons
 
 
        if(have_to_swap){
            current_node = this->bubble_down(current_node);
        }
 
    } while(have_to_swap);
}
 
#endif

Voici les points qui me chagrinent (désolé il y en a beaucoup) :

- Bien que l'attribut elements_ de type elements qui est un typedef de std::vector<Tkey> soit déclaré protected je n'arrive pas à m'en servir directement dans la sous classe MinHeap, bizarrement je dois écrire this->elements_ . Or j'avais déjà écrit des classes qui héritaient d'autres classes (mais sans template) et je pouvais juste écrire elements_.

- Le typedef elements n'est pas transmis à la classe fille, est-ce normal ?

- chose assez extraordinaire je trouve : typedef unsigned int node est très bien compris dans la classe mère mais pas dans la classe fille, j'ai dû le sortir de la classe pour éviter d'avoir les erreurs 'node' n'est pas un type.

- J'ai finalement pu compiler mes deux classes (ce qui ne me satisfait pas car je ne comprends pas les points plus haut mais passons pour le moment) : et j'ai voulu essayer quelque chose car que jtrouvais le tout un peu douteux, dans un fichier test j'ai créé un objet de la classe mère supposée non instanciable et le compilateur ne m'a pas crié dessus, j'ai aussi mis en commentaires une fonction virtuelle pure et le compilateur ne m'a pas dit que je n'avais pas définit cette fonction.

- Enfin j'ai essayé ceci

Code :

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

1
2
3
MinHeap<double> heap();
 
    heap.insert(13.2);

Il me dit que insert n'existe pas dans "heap" qui est de "non class type" MinHeap<double>()

Voilà ça en fait beaucoup si vous pouviez m'aider à comprendre 1 ou plusieurs de ces points je vous en serais très reconnaissant merci.

Immo

[jo_link_noir]

- Bien que l'attribut elements_ de type elements qui est un typedef de std::vector<Tkey> soit déclaré protected je n'arrive pas à m'en servir directement dans la sous classe MinHeap, bizarrement je dois écrire this->elements_ .

- Le typedef elements n'est pas transmis à la classe fille, est-ce normal ?

http://en.cppreference.com/w/cpp/lan...dependent_name
Pour faire un gros résumé: L'utilisation de classe template dépendent des paramètres template (logique), et le compilateur ne cherche que les relations sans dépendance. Pour outrepasser cette règle, il faut lui indiquer un contexte de recherche (this pour les membre ou typename Heap<Tkey>::le_type pour les types).

- chose assez extraordinaire je trouve : typedef unsigned int node est très bien compris dans la classe mère mais pas dans la classe fille, j'ai dû le sortir de la classe pour éviter d'avoir les erreurs 'node' n'est pas un type.

À mon avis, tu as oublié de mettre MinHeap<Tkey>:: devant node.

- dans un fichier test j'ai créé un objet de la classe mère supposée non instanciable et le compilateur ne m'a pas crié dessus, j'ai aussi mis en commentaires une fonction virtuelle pure et le compilateur ne m'a pas dit que je n'avais pas définit cette fonction.

On n'a pas le même compilateur alors ^^.
Pour commencer, heapify ne peut pas compiler, car retourne un type abstrait.

- Enfin j'ai essayé ceci

Code :

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

1
2
3
MinHeap<double> heap();
 
    heap.insert(13.2);

En fait, heap est ici une fonction à cause des parenthèse vide (il n'en fait pas), C'est pour cette raison que c++11 introduit la construction généralisé avec des accolades: MinHeap<double> heap{};.

[ImmoTPA]

Tout d'abord merci à toi Jo-link-noir.

J'ai pu réglé certains des problèmes mais pas tous. Si tu le veux bien j'ai encore deux ou trois questions.

Comment se fait-il que dans heap.hpp le compilateur me dise "cannot allocate an object of abstract type Heap<double>" dans la fonction bubble up. La fonction renvoit void et ne fait que swap deux éléments. Y-a-t-il un moyen de lui dire : "certes tu es une classe abstraite mais pas tes classes filles et elles peuvent toutes les deux appeler heapify et heapify devrait faire la meme chose pour les deux donc jvoudrais ne pas la redéfinir deux fois

Pour le typedef, je sais que si je mets typename MinHeap<Tkey>::node cela fonctionne, ce que je ne comprends pas c'est pourquoi c'est nécessaire ici quand il me suffisait d'écrire node pour la classe Min ? Et sais-tu pourquoi le typedef n'a pas simplement été hérité par la classe MinHeap ?

Merci beaucoup de ton aide encore une fois

[Bousk]

Pourrait-on voir les messages d'erreur complet ?
Je ne vois pas pourquoi tu parles de Heap dans bubble_up. Par contre ta fonction heapify ne marchera pas, comme il a été dit plus haut. Elle retourne par copie un Heap<TKey> qui est abstraite.

Le typedef doit marcher, mais il faut le spécifier entièrement. Les classes templates sont des choses bien chiantes

[ImmoTPA]

Bonjour Bousk et merci de ton aide à toi aussi. Voici mes nouveaux messages d'erreurs.

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
heap.hpp: In instantiation of ‘class Heap<double>’:
min_heap.hpp:10:7:   required from ‘class MinHeap<double>’
test.cpp:6:21:   required from here
heap.hpp:58:12: error: cannot allocate an object of abstract type ‘Heap<double>’
 void Heap<Tkey>::bubble_up(const node n){
            ^
heap.hpp:12:7: note:   because the following virtual functions are pure within ‘Heap<double>’:
 class Heap {
       ^
heap.hpp:31:18: note: 	Heap<Tkey>::node Heap<Tkey>::bubble_down(Heap<Tkey>::node) [with Tkey = double; Heap<Tkey>::node = unsigned int]
     virtual node bubble_down(const node n) = 0;          // need to be specialized (Min or Max Heap ? )
                  ^
heap.hpp:32:18: note: 	void Heap<Tkey>::percolate_up(Heap<Tkey>::node) [with Tkey = double; Heap<Tkey>::node = unsigned int]
     virtual void percolate_up(const node n_start) = 0;   
                  ^
heap.hpp:33:18: note: 	void Heap<Tkey>::percolate_down(Heap<Tkey>::node) [with Tkey = double; Heap<Tkey>::node = unsigned int]
     virtual void percolate_down(const node n_start) = 0;

Je comprends qu'on ne puisse pas instancier une classe abstraite mais quel rapport avec ma fonction bubble_up ?

Code :

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

1
2
3
4
template <typename Tkey>
void Heap<Tkey>::bubble_up(const node n){
    std::swap(elements_[n], elements_[daddy(n)]);
}

Voici ce que j'aimerai faire, si vous savez comment faire ou si ce n'est pas possible j'apprécierai beaucoup que vous me le disiez !

Bubble_up ne dépend pas du type de Heap que j'instancie (Min ou Max que je n'ai pas encore codé), je voudrais donc la coder une seule fois dans Heap et ensuite un objet de type MinHeap ou MinMax pourra appeler cette fonction sans qu'elle soit redéfinie dans MinHeap ou MaxHeap.

Pour heapify : pour le coup je suis moins sur que ce soit possible mais je demande quand même. Cette fonction dépend de la spécialisation de Heap en ce sens que elle n'est pas la même selon MinHeap ou MaxHeap. En effet elle renvoie dans un cas un MinHeap et dans l'autre un MaxHeap, à l'intérieur de la fonction la fonction percolate_down (virtuelle pure) est appelée.

Voici ce que j'espérais mais dont je doute que ce soit possible :

renvoyer un Heap, pour savoir lequel (Min Ou Max), j'espérais qu'il y aurait une syntaxe possible, et que la fonction percolate_down s'adapte à l'objet par lequel elle est appelée. Exemple :

MinHeap<double>::heapify(un_vector); // appelle à l'intérieur percolate_down de MinHeap<double> et renvoie un MinHeap
MaxHeap<double>::heapify(un_autre_vector); // appelle à l'intérieur percolate_down de MaxHeap<double> et renvoie un MaxHeap

Je comprendrai que pour heapify je sois obligé de la définir deux fois, dans MinHeap et dans MaxHeap même si en fait elles font la même chose pour ainsi dire.

Par contre il doit y avoir un moyen de ne pas avoir à définir bubble_up dans les classes filles vu qu'elle est exactement pareil dans les deux cas !

Merci beaucoup

[koala01]

Salut,

Les messages du compilateur sont parfois chiants à décoder, mais il te fournissent pourtant toutes les informations utiles

Ainsi, à la ligne 4 du message d'erreur, on peut lire

Code :

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

1
2
heap.hpp:58:12: error: cannot allocate an object of abstract type ‘Heap<double>’
 void Heap<Tkey>::bubble_up(const node n){

et, gentil comme il est, il continue (lignes 5 et suivantes) en t'indiquant

Code :

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

1
2
3
4
5
6
7
8
9
10
11
heap.hpp:12:7: note:   because the following virtual functions are pure within ‘Heap<double>’:
 class Heap {
       ^
heap.hpp:31:18: note: 	Heap<Tkey>::node Heap<Tkey>::bubble_down(Heap<Tkey>::node) [with Tkey = double; Heap<Tkey>::node = unsigned int]
     virtual node bubble_down(const node n) = 0;          // need to be specialized (Min or Max Heap ? )
                  ^
heap.hpp:32:18: note: 	void Heap<Tkey>::percolate_up(Heap<Tkey>::node) [with Tkey = double; Heap<Tkey>::node = unsigned int]
     virtual void percolate_up(const node n_start) = 0;   
                  ^
heap.hpp:33:18: note: 	void Heap<Tkey>::percolate_down(Heap<Tkey>::node) [with Tkey = double; Heap<Tkey>::node = unsigned int]
     virtual void percolate_down(const node n_start) = 0;

Du coup, tu as toutes tes réponse : le problème survient à la ligne 58 de heap.hpp car tu essaye de créer une instance de la classe Heap, spécialisée pour le type double, mais Heap<T>(et donc Heap<double>) est une classe abstraite, à cause de la présence des fonctions virutelles pures non définies (normal, c'est la classe de base ) nommée bubble_down (déclarée en ligne 31) percolate_up (déclarée en ligne 32) et percolate_down (déclarée en ligne 33).

Ceci dit, il faut aussi comprendre que le principe des classes template est de demander au compilateur de générer du code binaire en fonction des types donnés comme paramètres template. Mais cela signifie que tout le travail se fait ... à la compilation (par opposition au choix de la "version" d'une fonction virtuelle qui a lieu à l'exécution) et, surtout, que le principe de la programmation générique est de partir de l'idée que, si on ne sait pas quelle type de donnée sera manipulée, on sait en revanche comment cette donnée sera manipulée.

Tout cela pour dire que l'on peut profiter d'un certain type de polymorphisme en programmation générique (le polymorphisme dit "paramétrique"), mais que cela n'a rien à voir avec le polymorphisme auquel on pense lorsque l'on parle de polymorphisme (associé aux habituelles fonctions virtuelles) "classique" et dont le vrai nom est "polymorphisme d'inclusion".

Tu n'auras jamais de problème à faire hériter une classe template d'une classe non template en redéfinissant les comportements des fonctions membres virtuelles dans la classe template.

Par contre, il est beaucoup plus compliqué de travailler avec une classe template comme classe de base lorsque cette classe doit exposer des fonctions virtuelles et en particulier si ces fonctions virtuelles sont en réalité des fonctions virtuelles pures.

Ceci dit, quelqu'un a dit (était-ce donald knuth ) que tout problème en informatique peut être résolu en ajoutant un niveau d'abstraction supplémentaire.

En modifiant ta classe Heap pour qu'elle connaisse le type de la classe qui en dérive (on appelle cela le CRTP) et en créant les foncteurs adéquats, tu pourrais parfaitement remplacer les fonctions virtuelles pures par des fonctions qui font appel aux foncteurs qui t'intéressent

A titre exceptionnel, le code que voici n'a pas été testé, mais il devrait te donner la base de départ
on commence donc par modifier la classe heap sous une forme proche de

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
template <typename Key,
          typename CRTP> // le type de la classe dérivée (ex: MinHeap<T>)
class Heap{
// Simplifions nous la vies, créons quelques alias de type bien utiles :D
    using bubble_down_t = typename CRTP::bubble_down_t ; // le foncteur pour bubble_down;
    using percolate_up_t = typename CRTP::percolate_up_t; // le foncteur pour percolate_up;
    using percolate_down_t = typename CRTP::percolate_down_t; // le foncteur pour percolate_down;
public: 
    /*je passe sur tout ce qui n'est pas fonction virtuelle pure ;) */
    /* bubble_down renvoie le résultat renvoyé par le foncteur bubble_down */
    node bubble_down(const node n){
        return bubble_dow_t::apply(n);
    }
    // il percolate_up et percolate_down utilisent les foncteurs correspondant
    void percolate_up(const node n_start){
        percolate_up_t::apply(n_start);
    }   
    void percolate_down(const node n_start){
        percolate_down_t(n_start);
    }
};

Puis, pour chaque comportement spécifique, tu crées une structure qui expose une fonction statique apply qui correspond au comportement attendu, cela prendra une forme proche de

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* un premier comportement pour bubble_down*/
template <typename NodeT>
struct BubbleDown_1{
    static NodeT apply(NodeT){
        /* ce qui doit être fait */
        return blabla;
    }
};
/* un deuxième comportement pour bubble_down*/
template <typename NodeT>
struct BubbleDown_2{
    static NodeT apply(NodeT){
        /* ce qui doit être fait */
        return blabla;
    }
};
/* un premier comportement pour percolate_up*/
template <typename NodeT>
struct PercolateUp_1{
    static void apply( const NodeT){
        /* ce qui doit être fait */
 
    }
};
/* un deuxième comportement pour percolate_up*/
template <typename NodeT>
struct PercolateUp_2{
    static void apply( const NodeT){
        /* ce qui doit être fait */
 
    }
};
 
/* un premier comportement pour percolate_down*/
template <typename NodeT>
struct PercolateDown_1{
    static void apply( const NodeT){
        /* ce qui doit être fait */
 
    }
};
/* un deuxieme comportement pour percolate_down*/
template <typename NodeT>
struct PercolateDown_2{
    static void apply( const NodeT){
        /* ce qui doit être fait */
 
    }
};

(bien sur, tu peux avoir autant de comportement que tu le souhaite, hein )
(NOTA: J'ai opté pour des fonctions statiques apply(), j'aurais pu envisager l'utilisation de operator() et créer de vrais foncteurs... Le choix t'appartient )
Une fois que tu as cela, tu peux créer tes classes dérivées, par exemple, une classe pour lesquels ce sont à chaque fois les premiers comportements qui sont observés. Tout ce que tu as à faire, c'est à créer un alisas de type sur la structure qui t'intéresse pour chaque comportement . Cela pourrait prendre une forme proche de

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
26
27
template <typename Key>
class Derivee1 : public Heap<Key, Derivee1<Key>>{
public:
    /* toute la magie réside dans ces trois lignes */
    using bubble_down_t = BubbleDown_1;
    using percolate_up_t = PercolateUp_1;
    using percolate_Down_t = PercolateDown_1;
};
template <typename Key>
class Derivee2 : public Heap<Key, Derivee2<Key>>{
public:
    /* toute la magie réside dans ces trois lignes */
    using bubble_down_t = BubbleDown_2;
    using percolate_up_t = PercolateUp_2;
    using percolate_Down_t = PercolateDown_2;
};
/* Tant que les signatures de fonctions correspondent, tu peux faire ce 
  * que tu veux... si cela a du sens ;)
  */
template <typename Key>
class Derivee3 : public Heap<Key, Derivee3<Key>>{
public:
    /* toute la magie réside dans ces trois lignes */
    using bubble_down_t = BubbleDown_1;
    using percolate_up_t = PercolateUp_2;
    using percolate_Down_t = PercolateUp_1;
};