template et héritage

Version imprimable

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:

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:

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:

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

19/05/2015, 19h45
jo_link_noir
Citation:

Envoyé par ImmoTPA

- 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).

Citation:

Envoyé par ImmoTPA

- 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.

Citation:

Envoyé par ImmoTPA

- 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.
Citation:
Envoyé par ImmoTPA

- Enfin j'ai essayé ceci

Code:

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{};.
20/05/2015, 04h10
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 :)
20/05/2015, 09h49
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 :)

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

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:

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 :)

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:

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:

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 :D ) 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 :question:) 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:

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:

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:

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; };

D'ailleurs, à bien y réfléchir, si la seule différence qu'il existe entre les différentes classes dérivées de Heap réside effectivement dans le comportement des fonctions bubble_down et percolate_x, tu peux très bien "simplifier" le tout en une seule classe, fournissant des paramètres template pour les différentes structures au lieu d'utiliser le CRTP.

Cela prendrait alors une forme proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 template <typename T, template<typename> class B, //bubble_donw_t template <typename> class PU, //percolate_up_t template <typename> class PD> //percolate_down_t class Heap { /* la seule différence par rapport au message précédant tient dans les * alias de types */ using bubble_down_t = B<T>; using percolate_up_t = PU<T>; using percolate_down_t = PD<T>; public: 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); } };
ATTENTION !!! Comme Heap<int, BubbleDown1, PercolateUp_1, PercolateDown_1> est un type différent de Heap<int, BubbleDown1, PercolateUp_1, PercolateDown_2>[/codeinline], tu ne peux pas placer ces deux types dans une seule et meme collection (ex std::vector<Heap<...>>)

20/05/2015, 17h31
ImmoTPA

Ouaou c'est du costaud Oo. En tout cas merci de ta réponse Koala j'apprécie énormément. En revanche j'ai deux trois questions comme tu peux l'imaginer : la première, plus une confirmation. Je croyais que la syntaxe suivante (par exemple)

void MinHeap<Tkey>::heapify(void);

signifiait "la fonction heapify qui ne prend pas d'argument, ne retourne aucun argument et se trouve dans la classe MinHeap<Tkey>, or d'après le compilateur qui s'énerve en me disant que j'essaie d'instancier une classe abstraite il semblerait que ça ait une autre signification, pourrais-tu me l'expliquer s'il te plait ?

Si j'ai compris un minimum au premier passage de ce que tu as écrit, si mon but c'est d'écrire deux classes instanciables claires et bien séparées MinHeap qui permet de créer un tas min et MaxHeap qui permet de créer un tas max il vaudrait mieux la première solution que la deuxième ? La deuxième jouant plutôt sur les comportements des fonctions qui diffèrent pour paramétrer une seule classe Heap qui pourrait alors être selon mon bon vouloir un MinHeap ou un MaxHeap ?

A quoi sert le using dans

Code:

using bubble_down_t = typename CRTP::bubble_down_t

par exemple ?

Merci à tous en tout cas.
20/05/2015, 18h00
ImmoTPA

Par contre je suis un peu perdu, du coup avec ta solution les fonctions percolate_down percolate_up et bubble_down ne sont plus virtuelles pures et Heap est instanciable nan ?

J'ai peut être très mal lu, mais la seule fonction heapify que j'ai trouvée est dans Heap<T>...

Ceci dit : pour pouvoir profiter du polymorphisme (d'inclusion :D), il faut impérativement deux choses :

que tu travailles avec une référence (ou un pointeur) sur l'objet qui t'intéresse, si tu ne le connais que comme étant du type de base
que la fonction soit virtuelle (pour indiquer au compilateur qu'il devra s'attendre à trouver des redéfinitions du comportements de la fonction dans les classes dérivées)

La première condition est réellement indispensable, autrement, lorsque tu passe l'objet par valeur, tu effectue une copie de "la partie correspondant à la classe de base" et tu as un effet de "slicing" qui fait que le compilateur ne se rend même plus compte qu'il travail sur un objet du type dérivé

La deuxième condition est tout aussi indispensable car, si tu connais un objet de type MinHeap comme étant (une référence ou un pointeur sur) un objet de type Heap, le compilateur ne mettra pas en place la mécanique qui permet d'appeler le comportement de MinHeap et appellera la version ... Heap de la fonction.

Si les deux conditions ne sont pas remplies, il ne faut pas t'étonner s'il te crie dessus parce que heap est une classe abstraite ;)

Citation:

Si j'ai compris un minimum au premier passage de ce que tu as écrit, si mon but c'est d'écrire deux classes instanciables claires et bien séparées MinHeap qui permet de créer un tas min et MaxHeap qui permet de créer un tas max il vaudrait mieux la première solution que la deuxième ? La deuxième jouant plutôt sur les comportements des fonctions qui diffèrent pour paramétrer une seule classe Heap qui pourrait alors être selon mon bon vouloir un MinHeap ou un MaxHeap ?

En fait, le code de mes deux interventions précédantes aboutira toujours au même résultat car la version qui utilise l'héritage aura pour effet d'avoir un type Heap<T,MinHeap<T>> et un type Heap<T>,MaxHeap<T>> qui sont forcément des types différents, vu que l'un des paramètres template est différent. Par contre, cela te permet effectivement d'instancier "explicitement" un objet de type MinHeap et un autre de type MaxHeap.

La version de ma deuxième intervention fait que tu n'as pas (forcément) de différence entre ces deux notions : ce sont à chaque fois des Heap, dont le comportement variera en fonctions des paramètres template que tu fourniras lors de l'instanciation ;) (*)

(*) Ceci dit, il est tout à fait possible de retrouver des types MinHeap et MaxHeap à l'aide d'alias de types ;)(**)

Citation:

A quoi sert le using dans

Code:

using bubble_down_t = typename CRTP::bubble_down_t;

En fait, C++11 est arrivé avec une nouvelle syntaxe (plus souple) pour déclarer des alias de type... Ce code est donc strictement identique à

Code:

typedef typename CRTP::bubble_down_t bubble_down_t;

Mais tu ne pourrais pas utiliser typedef pour déclarer un alias de type MinHea<T> comme étant une spécialisation partielle de Heap (**):
Code:

1 2 template <typename T> typedef Heap<T, BubbleDown1, PercolateUp1, PercolateDown1> MinHeap<T> ; // refusé à cause des restrictions du mot clé typedef
, tout ce que tu pourrais faire, c'est un typedef sur des spécialisations totales :
Code:

1 2 3 4 5 6 typedef Heap<double, BubbleDown1, PercolateUp1, PercolateDown1> MinHeap_double ; typedef Heap<float, BubbleDown1, PercolateUp1, PercolateDown1> MinHeap_float ; typedef Heap<int, BubbleDown1, PercolateUp1, PercolateDown1> MinHeap_int ; typedef Heap<long double, BubbleDown1, PercolateUp1, PercolateDown1> MinHeap_longdouble ; /* ... */
ce qui reste malgré tout assez dommage.

La nouvelle syntaxe (celle qui utilise le mot clé using) est beaucoup plus souple et te permet de créer un alias de type avec une spécialisation partielle sous la forme de
Code:

1 2 3 4 template <typename T> using MinHeap<T> = Heap<T, BubbleDown1, PercolateUp1, PercolateDown1>; template <typename T> using MaxHeap<T> = Heap<T, BubbleDown1, PercolateUp1, PercolateDown1>;
que tu pourrais alors utiliser sous une forme proche de
Code:

1 2 MinHeap<int> minInt; maxHeap<double> maxDouble;
Par habitude (et parce que cela permet de garder un code homogène), j'utilise la syntaxe à base de using pour tous les alias de types que je dois créer...

En plus, je la trouve plus facile à suivre car :

le nom de l'alias arrive en premier
il y a un caractère spécifique ( '=') qui sépare l'alias du type d'origine

20/05/2015, 18h17
koala01

Citation:

Envoyé par ImmoTPA

Par contre je suis un peu perdu, du coup avec ta solution les fonctions percolate_down percolate_up et bubble_down ne sont plus virtuelles pures et Heap est instanciable nan ?

Oui, tout à fait... Mais comme tu dois de toutes manières préciser soit la classe dérivée pour la version qui utilise le CRTP soit les structures (implémentant une fonction apply() ) qui permettent d'effectuer les traitement relatifs à bubble et à percolate_X, cela ne posera pas de problème ;)
20/05/2015, 18h37
ImmoTPA

Daccord, je te remercier beaucoup de ta patience et de tes explications. Néanmoins pour ma part le but c'est ça :

Heap<Tkey> heap{}; // pas bon car Heap n'est pas instanciable (en remplaçant Tkey par un type qui implémente operator<)

MinHeap<Tkey> min_heap MinHeap{}: // crée un tas (heap) min (en remplaçant Tkey par un type qui implémente operator<)

MaxHeap<Tkey> max_heap MaxHeap{}; // crée un tas (hea) max (en remplaçant Tkey par un type qui implémente operator<)

Et bien que ce que tu m'as montré est sacrément puissant et intéressant, c'est à cela que je veux arriver vraiment. Maintenant la question c'est de le faire élégamment de manière à ne pas dupliquer du code si ce n'est pas nécessaire.

Si tu comprends ce que je veux faire, comment le ferais-tu ?

Dans mon idée j'implémente dans Heap les fonctions membres qui ne changent pas pour MinHeap ou MaxHeap de manière à simplement ne pas les redéfinir et un objet MinHeap ou MaxHeap appelera seulement la fonction membre de la classe mère.

Je veux écrire les fonctions suivantes différemment dans MinHeap et MaxHeap car elles n'ont pas le même comportement : percolate_up, percolate_down, bubble_down

Je veux aussi écrire la fonction suivante dans MinHeap et MaxHeap mais je veux aussi qu'elle soit static car elle n'a pas besoin d'un objet de la classe pour être appeler : heapify

As-tu une idée sur la manière de faire ça sans créer une seule classe de base paramétrée comme tu me l'as montré ou est-ce la seule solution ?

Dans le pire des cas pourrais-je simplement ne pas déclarer les fonctions dans la classe mère mais seulement dans les classes filles ? (même si je trouve cela moins élégant)

Merci encore

Citation:

Envoyé par ImmoTPA

Daccord, je te remercier beaucoup de ta patience et de tes explications. Néanmoins pour ma part le but c'est ça :

Heap<Tkey> heap{}; // pas bon car Heap n'est pas instanciable (en remplaçant Tkey par un type qui implémente operator<)

MinHeap<Tkey> min_heap MinHeap{}: // crée un tas (heap) min (en remplaçant Tkey par un type qui implémente operator<)

MaxHeap<Tkey> max_heap MaxHeap{}; // crée un tas (hea) max (en remplaçant Tkey par un type qui implémente operator<)

Et bien que ce que tu m'as montré est sacrément puissant et intéressant, c'est à cela que je veux arriver vraiment. Maintenant la question c'est de le faire élégamment de manière à ne pas dupliquer du code si ce n'est pas nécessaire.

Si tu comprends ce que je veux faire, comment le ferais-tu ?

Dans mon idée j'implémente dans Heap les fonctions membres qui ne changent pas pour MinHeap ou MaxHeap de manière à simplement ne pas les redéfinir et un objet MinHeap ou MaxHeap appelera seulement la fonction membre de la classe mère.

Je veux écrire les fonctions suivantes différemment dans MinHeap et MaxHeap car elles n'ont pas le même comportement : percolate_up, percolate_down, bubble_down

Tout celà, tu l'as avec les deux versions ;)

Citation:

Je veux aussi écrire la fonction suivante dans MinHeap et MaxHeap mais je veux aussi qu'elle soit static car elle n'a pas besoin d'un objet de la classe pour être appeler : heapify

Pour heapify, la version paramétrée (comprend : sans héritage) est sans doute la meilleure, car il suffit d'ajouter un paramètre template représentant une structure qui fait ce que tu attends sous une forme proche de
Code:

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 template <typename T, template<typename> class B, //bubble_donw_t template <typename> class PU, //percolate_up_t template <typename> class PD, //percolate_down_t template <typename > class H>//heapify class Heap { /* la seule différence par rapport au message précédant tient dans les * alias de types */ using bubble_down_t = B<T>; using percolate_up_t = PU<T>; using percolate_down_t = PD<T>; using hepify_t = H<T>; public: 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::apply(n_start); } static void heapify(/* ... */){ heapify_t:apply(/*...*/); } };
NOTA:j'ai mis des commentaires pour les arguments, à toi de voir s'il en faut ;)

Tu pourrais d'ailleurs prévoir une généralisation supplémentaire de heapify sous une forme proche de (attention, accroche toi :D)
Code:

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 template <typename T, template<typename> class B, //bubble_donw_t template <typename> class PU, //percolate_up_t template <typename> class PD, //percolate_down_t template <typename > class H>//heapify class Heap { /* la seule différence par rapport au message précédant tient dans les * alias de types */ using bubble_down_t = B<T>; using percolate_up_t = PU<T>; using percolate_down_t = PD<T>; using hepify_t = H<T>; public: 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::apply(n_start); } template <typename ... PARAMS> // toute la magie est là static void heapify(PARAMS ... p){ heapify_t:apply(p ... ); } };
(ca, ce sont des variadic template, utilisable à partir de C++11, qui permettent de désigner "n'importe quel nombre d'argument de n'importe quel type... Dans le genre générique, on fait pas mieux :D)

Citation:

As-tu une idée sur la manière de faire ça sans créer une seule classe de base paramétrée comme tu me l'as montré ou est-ce la seule solution ?

Il faut savoir que l'héritage (public) est la relation la plus forte qui puisse exister entre deux classes. Cela signifie que c'est la relation qu'il ne faut utiliser que si l'on n'a vraiment pas d'autre choix.

On pourrait parfaitement utiliser l'exemple que j'ai donné dans mon premier exemple et "simplement" rajouter une fonction statique heapify dans chaque classe dérivée de Heap<T>.

Cependant, je ne crois pas que l'on ai réellement intérêt à forcer le développeur à recourir d'office à l'héritage publique (c'est rarement le cas avec des classes template, à l'exception des classes qui n'exposent qu'une interface qui n'a aucun sens si elle est utilisée seule ;) )

Citation:

Dans le pire des cas pourrais-je simplement ne pas déclarer les fonctions dans la classe mère mais seulement dans les classes filles ? (même si je trouve cela moins élégant)

Bien sur que tu le pourrais... Mais, cela signifie que tu es obligé soit de connaitre les instances des classes dérivées comme étant du type de la classe dérivée, soit de passer par un double dispatch si tu ne connais à la base les différentes instances que comme étant (des pointeurs ou des références sur) des objets du type de la classe de base.

Et cela m'amène à une autre question (que j'aurais déjà du poser depuis longtemps ) : as-tu réellement besoin du polymorphisme "classique" (comprend : le polymorphisme d'inclusion, celui qui est mis en place avec les fonctions virtuelles) :question: Autrement dit, est-ce que tu envisage, d'une manière ou d'une autre, d'avoir une collection connue comme contenant des pointeurs (de préférence intelligent) vers Heap<T> qui pourrait contenir à la fois des MinHeap<T> et des MaxHeap<T> sous une forme qui pourrait être proche de std::vector<std::unique_ptr<Heap<int>>;.

Si tu es confronté à un tel besoin, il faudra veiller à respecter la sémantique d'entité associée aux classes intervenant dans une hiérarchie e classes, et donc à rendre Heap<T> non copiable et non affectable.

Si tu n'es pas confronté à ce genre de besoin, tu n'as pas vraiment besoin de l'héritage public et la solution à base de paramètres template pour bubble, percoleX et heapify -- éventuellement associée à quelques alias de type partiels -- semble réellement être la "moins mauvaise" solution ;)

21/05/2015, 07h38
ImmoTPA

Bonjour, et merci encore de ta réponse. Pour répondre à ta question, la classe Heap que je veux créer sert à créer pour certains algorithmes une file de priorité. Donc je suis sûr à 99.99% que je ne créerai pas une collection de Heap encore moins de HeapMin et Max mélangés.

Je vais donc essayer la méthode 1 :).
21/05/2015, 12h37
koala01

Citation:

Envoyé par ImmoTPA

Bonjour, et merci encore de ta réponse. Pour répondre à ta question, la classe Heap que je veux créer sert à créer pour certains algorithmes une file de priorité. Donc je suis sûr à 99.99% que je ne créerai pas une collection de Heap encore moins de HeapMin et Max mélangés.

Alors, la solution qui consiste à avoir un paramètre template par algorithme "particulier" est la plus simple et la plus efficace... Car tout sera des Heap (modulo d'éventuels alias de type partiels) mettant des algorithmes particuliers enoeuvre ;)
24/05/2015, 18h18
ImmoTPA

Hey Koala ! j'ai été pas mal occupé mais là j'essaie d'implémenter ce que tu m'as montré, j'en profite pour te poser deux ou trois autres questions si ça ne t'ennuie pas.

La première : est ce que je peux appliquer ta méthode avec tes foncteurs avec une fonction membre statique comme heapify ?

La seconde : j'ai lu suite à ce que tu m'as dit ici sur internet le fait que beaucoup de gens code des relations d'héritage à outrance. Pour ma part j'ai appris à l'école que quand on peut dire "A est un B" (comprendre, tout ce que peux faire et tout ce qu'est un B, un A peut le faire aussi et l'est aussi), alors une bonne implémentation consiste à faire hériter A de B. Ta définition diffère-t-elle ? si oui en quoi ?

La troisième : pour les fonctions static apply : je ne peux pas accéder à mes fonctions membres par this->fonction vu que c'est une méthode statique, dois-je déclarer
static NodeT apply(NodeT n, MinHeap<Tkey>& heap) ?

La quatrième (c'est la 3e fois que jmodifie le message) : comment je fais si dans ma structure PercolateDown la fonction apply doit appliquer apply de la structure BubbleDown ?

La dernière : il y a souvent ce dilemme de savoir si on stock dans un std::vector par exemple plutôt une collection d'objets ou bien des pointeurs sur ces objets, pour ma part j'applique la règle, si les objets en question ont une raison d'être en dehors de la collection alors je mets des pointeurs sinon je stock directement les objets. Par exemple dans mon Heap, je stock des éléments, ces éléments n'existeraient pas si ils n'étaient pas voués à être stocké dans un Heap, je stock donc les éléments et non des pointeurs sur les éléments. Un contre-exemple serait par exemple, (j'invente un truc à la va-vite :) ) une classe vue comme un std::vector<*Etudiant>, les étudiants ayant probablement une autre raison d'être que celle d'appartenir à une classe (peut-être qu'ils peuvent aussi appartenir aussi à une chorale, un groupe de soutien, whatever).

Est-ce une bonne règle ? Si non, comment toi tu fais ?
Merci beaucoup :)

Citation:

Envoyé par ImmoTPA

Hey Koala ! j'ai été pas mal occupé mais là j'essaie d'implémenter ce que tu m'as montré, j'en profite pour te poser deux ou trois autres questions si ça ne t'ennuie pas.

La première : est ce que je peux appliquer ta méthode avec tes foncteurs avec une fonction membre statique comme heapify ?

Désolé, j'arrive pas à suivre ton chemin de pensée, pourrais tu me donner un exemple de ce que tu veux faire :question

Citation:

La seconde : j'ai lu suite à ce que tu m'as dit ici sur internet le fait que beaucoup de gens code des relations d'héritage à outrance. Pour ma part j'ai appris à l'école que quand on peut dire "A est un B" (comprendre, tout ce que peux faire et tout ce qu'est un B, un A peut le faire aussi et l'est aussi), alors une bonne implémentation consiste à faire hériter A de B. Ta définition diffère-t-elle ? si oui en quoi ?

Oui, même si l'idée véhiculée par ce que tu as appris s'y retrouve. Car, pour considérer un héritage publique, il faut en effet pouvoir dire qu'un objet de la classe dérivée EST-UN objet de la classe de base. Mais pas en terme de fonctionnalités; plutôt en terme de sémantique (comprend : de la définition que l'on trouve dans le dictionnaire) . Par exemple : la déclaration d'une voiture, d'une moto et d'un camion indique à chaque fois qu'il s'agit d'un véhicule. Cela te permet de franchir la première étape ;).

Mais ce n'est pas tout car il faut surtout respecter le Principe de Substitution de Liskov (Liskov Substitution Principle ou LSP en anglais):

Citation:

Envoyé par Barbara Liskov (trad wikipedia

Si q(x) est une propriété démontrable pour tout objet x de type T, alors q(y) est vraie pour tout objet y de type S tel que S est un sous-type de T.

C'est à dire que si ta classe de base expose une fonction faitMachinChose, il faut qu'il y ait du sens à appeler cette fonction depuis un objet de la classe dérivée.

Enfin, il faut respecter les règles de la programmation par contrat au minimum en ce qui concerne les préconditions et les postconditions:

les préconditions ne peuvent pas être renforcées dans la classe dérivée et
les postconditions ne peuvent pas être diminuées dans la classe de dérivée.

Ainsi, un rectangle dispose de trois invariants : quatre cotés, quatre angles droits et coté égaux 2 à 2. Or, on apprend à l'école "qu'un carré est un rectangle disposant de 4 cotés égaux". Si on se limite à la relation "EST-UN", on aura tendance à envisager de faire hériter Carre de Rectangle.

Mais, si on y réfléchit bien, Carré présente un invariant (4 cotés égaux) qui est beaucoup plus fort que l'invariant équivalent (coté égaux 2 à 2) auquel est soumis Rectangle. Et, comme un invariant est à la fois une précondition (c'est un condition qui doit être vérifiée avant toute tentative d'accès à notre objet) et une postcondition (elle doit être vérifiée après toute modification), on se rend compte le fait de faire hériter Carre de Rectangle contreviendrait à la première règle : une des préconditions serait renforcée dans la classe dérivée.

"Pas de problème" vas-tu me dire, "faisons hériter Rectangle de Carre"... Hé non, car, dans ce cas, la postcondition de Rectangles (coté égaux 2 à 2) serait diminuée par rapport à la postcondition équivalente de Carré (quatre cotés égaux).

C'est également la raison pour laquelle on ne peut pas faire hériter ListeTriee de Liste ou pour laquelle on ne peut sans doute pas faire hériter MinHeap (ou MaxHeap) de Heap : on trouvera surement un invariant dans ces classes qui dérogerait à l'une de ces règles ;)
Code:

1 2 3 La troisième : pour les fonctions static apply : je ne peux pas accéder à mes fonctions membres par this->fonction vu que c'est une méthode statique, dois-je déclarer static NodeT apply(NodeT n, MinHeap<Tkey>& heap) ?
Pas MinHeap, mais plutôt Heap<T, ...> ;) (car c'est définitivement la solution à préférer ;) )

Code:

La quatrième (c'est la 3e fois que jmodifie le message) : comment je fais si dans ma structure PercolateDown la fonction apply doit appliquer apply de la structure BubbleDown ?

As tu remarqué que les fonctions statiques portent systématiquement le même nom : apply :question: A vrai dire, j'aurais tout aussi bien pu créer un véritable foncteur qui n'aurait exposé que l'opérateur operator()(/* parametres */), cela serait revenu au même ;)

Mais, quoi qu'il en soit, cela implique que tant que la signature de la fonction apply correspond à l'appel qui en est fait, tu peux décider de modifier la structure au départ de laquelle cette fonction est appelée "à ta guise" (on appelle cela un "trait" ;) )

C'est la raison pour laquelle la solution la plus efficace consiste à ne pas utiliser l'héritage, mais à fournir un paramètre template désignant une structure exposant la fonction apply par fonction dont le comportement risque d'être redéfini.

Et s'il se fait que le comportement d'une des fonctions est en définitive identique à celui d'une structure qui a déjà été créé, rien ne t'interdit de faire du "recyclage", soit en utilisant directement cette structure comme paramètre template, soit en l'utilisant à l'intérieur d'une autre structure qui pourrait prendre la forme de
Code:

1 2 3 4 5 6 7 template <typename T> struct PercolateDown{ /* j'ai la flegme de vérifier le prototype de la fonction apply() pour cette structure ... */ bool apply(/* ... */){ return BubbleDown::apply(/* ... */) ; } };
L'énorme avantage de cette solution étant que tu crées effectivement une structure clairement distincte pour chaque utilisation, ce qui évitera au lecteur de ton code de se poser la question "mais pourquoi a-t-il donc fournit BubbleDown comme fonction à exécuter pour PercolateDown :question: il a perdu la tête :question:"... Mais les deux solutions sont tout à fait valides ;) :D

Citation:

La dernière : il y a souvent ce dilemme de savoir si on stock dans un std::vector par exemple plutôt une collection d'objets ou bien des pointeurs sur ces objets, pour ma part j'applique la règle, si les objets en question ont une raison d'être en dehors de la collection alors je mets des pointeurs sinon je stock directement les objets. Par exemple dans mon Heap, je stock des éléments, ces éléments n'existeraient pas si ils n'étaient pas voués à être stocké dans un Heap, je stock donc les éléments et non des pointeurs sur les éléments. Un contre-exemple serait par exemple, (j'invente un truc à la va-vite :) ) une classe vue comme un std::vector<*Etudiant>, les étudiants ayant probablement une autre raison d'être que celle d'appartenir à une classe (peut-être qu'ils peuvent aussi appartenir aussi à une chorale, un groupe de soutien, whatever).

Est-ce une bonne règle ? Si non, comment toi tu fais ?
Merci beaucoup :)

Je choisi de manière beaucoup plus simple, en fonction de la sémantique des éléments que je place dans la collection:

S'ils ont sémantique de valeur, je crée une collection d'objet (ex : std::vector<Couleur> )
S'ils ont sémantique d'entité, je crées une collection de pointeurs (de préférence intelligent) sur des objets (ex : std::vector<std::unique_ptr<Etudiants>>).

Après, il faut savoir que certains types ayant sémantique de valeur seront malgré tout très lourds à copier. Si l'on veut éviter la copie, on transmettra la collection sous la forme d'une référence éventuellement constante, si la fonction appelée ne doit pas en modifier le contenu (ex : void foo(std::vectr<Couleur> /* const */ & tab) ) voir, j'essayerai de fournir un intervalle représenté par deux itérateur à la fonciton (ex : template <typename ITER> void bar(ITER begin, ITER end), qui serait appelée sous la forme de bar(tab.begin(), tab.end()); )

Je préférerai d'ailleurs généralement la deuxième solution car elle apporte généralement une plus grande souplesse d'utilisation (on peut, par exemple, décider de changer le type de la collection "à notre guise", pour autant que le type d'itérateur reste compatible du moins, sans avoir à changer quoi que ce soit dans bar ;) )