[C++11] Queue / priority_queue et templates

Bonjour,

J'ai un algorithme identique qui utilise soit une queue soit une priority_queue et je voudrais généraliser cet algorithme pour qu'il fonctionne avec l'un ou l'autre des conteneurs. Voilà l'algo :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Fonction solve(file f, Noeud initial) current : Noeud // type   current <--- initial enfiler(current, f) TANT QUE (!vide(f)) current <--- defiler(f) // récupère le 1er noeud de la file ou le noeud avec le cout le plus faible dans le cas de la priority_queue POUR CHAQUE (succ : findSuccessors(current)) enfiler(succ, f) FIN POUR FIN TANT QUE FIN

---

Le problème est que dans le cas d'un queue pour défiler un Noeud, on utilise la fonction front() et dans le cas d'un priority_queue, elle s'appelle top() ... Y'a t-il un moyen de généraliser cette fonction solve à l'aide de template par exemple ? (je préfererais éviter de créer d'autres classes avec du polymorphisme pour résoudre ce problème si possible...)

J'espère que c'est clair ;)

Merci d'avance :)

Bonjour.

Je propose :

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 <class T, class Container> typename Container::const_reference getNext(const std::queue<T, Container>& q) { return q.front(); }   template <class T, class Container> typename Container::reference getNext(std::queue<T, Container>& q) { return q.front(); }   template <class T, class Container, class Compare> typename Container::const_reference getNext(const std::priority_queue<T, Container, Compare>& q) { return q.top(); }   template <class File, class Noeud> void solve(File& f, const Noeud& initial) { // ton code // Après un appel à "getNext(f)", ne pas oublier d'appeler "f.pop()". }

---

Edit 25/04/2016 à 19h30 : J'avais oublié d'utiliser le mot-clé typename.

Bonjour,

Ca ne compile pas, j'ai l'erreur :

Citation:

---

error: need 'typename' before 'Container::const_reference' because 'Container' is a dependent scope

---

Du coup, j'ai rajouté le typename devant, est ce que c'est correct ?

Autre chose, j'ai une erreur au link :

Citation:

---

undefined reference to `void Solver::solve<std::queue<Node*, std::deque<Node*, std::allocator<Node*> > > >()'

---

Voilà le code : (à noter que la fonction solve() est dans une classe Solver) :

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

template <class T, class Container> typename Container::const_reference getNext(const std::queue<T, Container>& q) { return q.front(); }   template <class T, class Container> typename Container::reference getNext(std::queue<T, Container>& q) { return q.front(); }   template <class T, class Container, class Compare> typename Container::const_reference getNext(const std::priority_queue<T, Container, Compare>& q) { return q.top(); }   template <class Container> void Solver::solve() { Container m_states; // le reste du code ici }   // Et l'appel de la fonction solve() dans le main : s->solve<std::queue<NODE*>>(); // avec NODE une classe normale

---

Merci

Citation:

---

Envoyé par Aspic

Ca ne compile pas, j'ai l'erreur :

Du coup, j'ai rajouté le typename devant, est ce que c'est correct ?

---

Tu as raison.
Ça m'apprendra à écrire du code sans vérifier que ça compile. :oops:

Citation:

---

Envoyé par Aspic

Autre chose, j'ai une erreur au link :

---

Le code suivant compile chez moi :

// Dans Solve.h :

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

#include <queue>   template <class T, class Container> typename Container::const_reference getNext(const std::queue<T, Container>& q) { return q.front(); }   template <class T, class Container> typename Container::reference getNext(std::queue<T, Container>& q) { return q.front(); }   template <class T, class Container, class Compare> typename Container::const_reference getNext(const std::priority_queue<T, Container, Compare>& q) { return q.top(); }   class Solver { public: template<class File> void solve(File& f, const int& noeudInitial) // J'ai mis int, mais il faudra le remplacer par le vrai type Noeud. { // pour voir si ça compile : getNext(f); f.pop(); } };

---

// Dans un fichier cpp :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

#include "Solve.h"   int _tmain(int argc, _TCHAR* argv[]) // j'utilise Visual C++ { // pour voir si ça compile : int noeudInitial = 0; Solver s; std::queue<int> file1; std::priority_queue<int> file2; s.solve(file1, noeudInitial); s.solve(file2, noeudInitial); return 0; }

---

Il faut que la définition de "solve" soit dans un fichier ".h" et que ce ".h" soit inclus dans le fichier ".cpp" qui appelle "solve".

Merci c'est vrai que avec les fonctions template, il ne faut pas oublier de mettre la définition dans le fichier .h et pas dans le .cpp !
J'oublie toujours ce détail et ca me saoule car j'aime bien séparer les prototypes des implémentations... ;)

Et oui ca marche maintenant ^^

Une petite remarque, pourquoi as tu deux fonctions getNext() pour la queue (une avec Container::const_reference et une autre avec Container::reference) alors qu'il n'y a qu'une seule fonction pour la priority_queue (Container::const_reference) ?

Citation:

---

Envoyé par Aspic

Une petite remarque, pourquoi as tu deux fonctions getNext() pour la queue (une avec Container::const_reference et une autre avec Container::reference) alors qu'il n'y a qu'une seule fonction pour la priority_queue (Container::const_reference) ?

---

Dans la documentation de la STL sur http://www.cplusplus.com, il existe deux fonctions std::queue::front (une constante et une non constante) alors qu'il n'existe qu'une seule fonction std::priority_queue::top (constante) :
http://www.cplusplus.com/reference/queue/queue/front/
http://www.cplusplus.com/reference/q...ity_queue/top/

Du coup, je n'ai pas pu faire de fonction :

Code:

---

1 2 3

template <class T, class Container, class Compare> typename Container::reference getNext(std::priority_queue<T, Container, Compare>& q);

---

Très bien, merci pour l'explication et ta réactivité :)