Discussion :

[Aspic]

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 :

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

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

[Pyramidev]

Bonjour.

Je propose :

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

[Aspic]

Bonjour,

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

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 :

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 c++ :

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

[Pyramidev]

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.

Autre chose, j'ai une erreur au link :

Le code suivant compile chez moi :

// Dans Solve.h :

Code c++ :

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
#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 c++ :

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

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

[Aspic]

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

[Pyramidev]

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 c++ :

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

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

[Aspic]

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