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