Bonjour a tous.
je ne suis pas encore tres familiarise avec toutes les subtilites du C++ et j'ai besoin de votre aide concernant un probleme.
J'ai reussi l'implementation d'une Queue marchant sur ce modele:
template <class Type> class Queue {
public:
Queue_Element<Type> *first;
Queue_Element<Type> *last;
int size_q;
Queue();
void push(Type item);
void pop();
Type& front();
Type& back();
int size();
bool empty();
friend ostream& operator << (ostream& os,Queue q)
}
//sachant que la classe representant un element de la queue est:
template <class Type> class Queue_Element {
public:
Type data;
Queue_Element *next;
Queue_Element();
Queue_Element(const Type &val);
~Queue_Element();
friend class Queue<Type>;
};
Je dois maintenant implementer un Queue qui gere la priorite des elements. c'est a dire que la seule difference avec la precedente, c'est que les elements ont un champs "priority" et que la fonction push de la Queue, au lieu d'inserer les element au debut de la liste, les range par priorite decroissante.
Bref je m'y retrouve pas entre l'heritage le polymorphisme et les modeles, mes essais n'ont pas reussis.
Si quelqu'un peu me donner le modele de ce que je dois faire (en gros) ca m'aiderait beaucoup, et pour les algorithmes je me debrouille!
Merci!
Et le fait est qu'implémenter un conteneur générique n'est pas anodin.
On va voir ça. Mais si tu me le permets, avant je vais faire quelques commentaires:
Il y a des points positifs dans ton code. Par exemple l'existence de deux méthodes distinctes front et pop, c'est très bien. :)
friend ostream& operator << (ostream& os,Queue q);est correct. Mais pour réduire les dépendances dans le code, on considère qu'il est mieux de déclarer global
ostream& operator << (ostream& os,Queue q);et son corps est alors ainsi
ostream& operator << (ostream& os,Queue q) { q.print(); }Où print est évidemment une méthode public de Queue.
par contre
N'est pas très bon. Il faudrait:
La référence, c'est pour éviter une copie non voulue de l'item au moment du placement dans la queue. Le const est là pour éviter d'éventuelles erreurs de codage plus tard et pour permettre au compilateur d'effecteur des optimisations dans certaines situations.
Ceci:
Est annonciateur de problème. La finalité de ces membres semble être de servir à parcourir le contenu de la queue. C'est certainement un itérateur qu'il faudrait...
et là ça ne va plus du tout, nous arrivons sur le problème annoncé plus haut.
//sachant que la classe representant un element de la queue est: template <class Type> class Queue_Element {Au départ tu essaies d'écrire une queue générique. c'est du moins ce que veux dire sa déclaration. Et un peu plus loin on voit que les éléments contenus ne peuvent pas être quelconques mais doivent détenir un pointeur sur le suivant, etc... et , ô hérésie, le type doit à l'avance connaître son conteneur puisque tu déclares la classe Queue amie de l'élément...
On dirait maintenant que tu codes une liste chaînée en C.
Mais plus du tout en C++ générique.
Donc avant de passer à ta queue à priorité, tu dois paufiner ta queue car elle ne marche pas en fait, contrairement à ce que tu semble penser. Elle en marche même pas du tout. Pardonne moi, mais c'est la réalité.
Elle marchera quand elle sera réellement générique, c'est à dire qu'il n'y aura aucune autre contrainte sur le type contenu autre le fait que son destructeur ne doive lever aucune exception.
Dans ce cas ta Queue fonctionnera peut être, si tant est que son code soit robuste aux exceptions, ce qu'il faudrait vérifier également.
Ceci fait tu pourrais passer à ta priory_queue (on dirait que tu t'exerces à ré-écrire le STL :) )
Basiquement et pour répondre enfin à ta question :) , une priority_queue est "tout simplement" (en théorie..) une queue donc le constructeur reçoit une fonction ou un objet fonction pour le tri des éléments. C'est donc relativement facile si la queue fonctionne. Mais cela implique probablement que la queue ait des iterateurs....
Bon courage. Tu t'es lancé dans un exercice ambitieux. Ecrire des conteneur génériques façon STL ça n'est pas de la tarte.... c'est même extrêmement difficile.
N'hésites pas à revenir sur ce forum, si tu en sens le besoin.
Je viens me corriger moi même :)
J'ai écrit dans lepost précédent
"Elle marchera quand elle sera réellement générique, c'est à dire qu'il n'y aura aucune autre contrainte sur le type contenu autre le fait que son destructeur ne doive lever aucune exception.
"
J'aurais du écrire:
"Elle marchera quand elle sera réellement générique, c'est à dire qu'il n'y aura aucune autre contrainte sur le type contenu que d'avoir une sémantique de valeur et que son destructeur ne leve aucune exception. "