utiliser des conteneurs triés stl pour pointeurs, utile?

Version imprimable

utiliser des conteneurs stl triés de pointeurs, definir critere comparaison

Bonjour,

Je début en programmation c++, mais j'ai tout de même une base.
pour un certain code j'ai voulu utiliser la stl afin de créer une liste triée d'objets.

Voici mon objet en très simplifié :
Code:

1 2 3 4 5 6 7 8 9 10 11 class Noeud { public: (constructeurs et autres...) int lireValeur() const {return Valeur;}; bool operator< (const Noeud & n2) {return (Valeur< n2.lireValeur()); private: int Valeur; autre déclarations... }
Il possède donc un opérateur de comparaison < surchargé pour comparer des objets entre eux. C'est l'opérateur choisi par défaut, si mes références sont bonnes, pour les conteneurs qui trient automatiquement les données, notamment priority_queue<> (ou map, set...)

J'ai voulu, parceque mon code a ce moment était plus facile à écrire comme ça, utiliser des pointeurs vers ces objets.

J'ai donc crée une liste: priority_queue<Noeud *> maListe; , et l'ai remplie avec des pointeurs vers mon objet. Mais évidemment, il ne les a pas du tout trié comme je voulais : c'est normal, une comparaison entre pointeurs ne compare pas les objets, mais les valeurs des pointeurs (c'est à dire des adresses mémoire, imprévisibles).

Alors ni une ni deux j'ai crée une fonction :
Code:

1 2 3 4 bool operator<(const Noeud * n1, const Noeud * n2) { return ( *n1 < *n2 ); }
et là... vlan ! ni une ni deux erreur :

Citation:

/Desktop/TP6/tp6.cpp:55: error: 'bool operator<(const Noeud*, const Noeud*)' must have an argument of class or enumerated type

Utiliser des pointeurs pour remplir mon tableau trié n'est pas une bonne idée, et je dois donc changer mon code pour y mettre les objets pointés directement ? ou alors c'est à ce moment qu'on doit utiliser ces fameuses classes de comparaison ou foncteurs? (et si oui comment ou alors avez vous un lien pour un exemple avec une utilisation claire?)

04/12/2007, 17h03
yan
ou as tu ecrit
Code:

1 2 3 bool operator<(const Noeud * n1, const Noeud * n2) { return ( *n1 < *n2 ); }
aprés la définition de la class Noeud?

[edit]
comment as tu defini ton priority_queue<> (ou map, set)
As mon avis un set est plus adapté a ce que tu veut faire
04/12/2007, 17h15
Pacorabanix

oui, la déclaration est bien après celle de la classe.

De toute façon j'ai mis des prototypes et les implémentations sont quant à elles vers la fin du fichier.

en ce moment dans mon code j'utilise une priority_queue<*Noeud, vector<*Noeud>>. j'ai aussi essayé avec priority_queue<*Noeud, deque<*Noeud>>.

En fait ce n'est qu'un conteneur très temporaire, le temps de construire mon propre conteneur (un arbre).

J'ai besoin d'avoir les objets en liste triée (ce seront les feuilles de mon futur arbre personnalisé), et je construit mon arbre personnalisé en extrayant continuellement les 2 noeuds les plus petits (ou les plus grands, peu importe, c'est un exercice scolaire pour nous apprendre à programmer un certain type d'arbre ;) ).

EDIT (précision): En me relisant on ne comprend pas bien pourquoi c'est important que j'ai une liste triée : c'est car 2 noeuds me permettent de créer un nouveau noeud (dont la valeur est la somme des plus petit) qui a en feuille les 2 noeuds de départ. ensuite les 2 noeuds de départ sont giclés de la liste et remplacés par le nouveau noeud. Ce dernier a une valeur plus grande et donc doit etre inséré correctement, pour que les 2 premiers noeuds de ma liste soit toujours ceux qui ont la plus petite valeur.

Je dois de toute façon finir par cet arbre personnalisé, le but était juste de stocker les objets de manière triée juste pour faciliter la construction de mon arbre. Donc s'il faut utiliser un set, je veux bien, mais mon bug persistera non ?
04/12/2007, 17h24
yan
???
Ca parait louche....

Code:

priority_queue<*Noeud, vector<*Noeud>>

A tien je viens de comprendre ton erreur

ca
Code:

1 2 3 bool operator<(const Noeud * n1, const Noeud * n2) { return ( *n1 < *n2 ); }
tu ne peut pas le déclarer :aie:

Il faut que tu écrite le test autrement :
Code:

1 2 3 bool ComparepNoeud(const Noeud * n1, const Noeud * n2) { return ( *n1 < *n2 ); }
puis tu défini ton contenaire comme :

std::set<Noeud*, &ComparepNoeud>
Pour la priority_queue je ne sait pas trop. Peut etre
std:: priority_queue<Noeud*, std::vector<Noeud*>,&ComparepNoeud>
04/12/2007, 17h44
Pacorabanix
Citation:
Envoyé par Mongaulois

???

Code:

1 2 3 bool operator<(const Noeud * n1, const Noeud * n2) { return ( *n1 < *n2 ); }

tu ne peut pas le déclarer :aie:

Il faut que tu écrite le test autrement :

Code:

1 2 3 bool ComparepNoeud(const Noeud * n1, const Noeud * n2) { return ( *n1 < *n2 ); }

puis tu défini ton contenaire comme :

std::set<Noeud*, &ComparepNoeud>
Pour la priority_queue je ne sait pas trop. Peut etre
std:: priority_queue<Noeud*, std::vector<Noeud*>,&ComparepNoeud>
Bon alors j'ai fait un set et une fonction :
Code:

1 2 3 4 5 6 bool ComparepNoeud(const Noeud * n1, const Noeud * n2) {...} (...) std::set<Noeud*, &ComparepNoeud> maListe;
mais il a pas l'air d'aimer.

(pareil avec priority_queue, et oui la syntaxe était correcte :

Citation:

tp6.cpp:137: error: template argument 2 is invalid
04/12/2007, 17h47
yan
Citation:
Envoyé par Pacorabanix

Bon alors j'ai fait un set et une fonction :

Code:

1 2 3 4 5 6 bool ComparepNoeud(const Noeud * n1, const Noeud * n2) {...} (...) std::set<Noeud*, &ComparepNoeud> maListe;

mais il a pas l'air d'aimer.
??comment ca il n'as pas l'aire d'aimer?
04/12/2007, 17h48
yan

au faite,
un set oblige que les objet soit unique.
Utilise plustôt multiset
dsl
04/12/2007, 17h51
Pacorabanix

Oui j'y ai pensé :D, pas de problème.

Par contre je ne comprend pas la déclaration std::multiset<Noeud*, &comparepNoeuds>.

&comparepNoeuds est un type ?
ou c'est l'adresse de la fonction comparepNoeuds ?

Je n'ai encore jamais utilisé de pointeurs ou de références vers des fonctions.
04/12/2007, 17h54
yan
Citation:

Envoyé par Pacorabanix

Oui j'y ai pensé :D, pas de problème.

Par contre je ne comprend pas la déclaration std::multiset<Noeud*, &comparepNoeuds>.

&comparepNoeuds est un type ?
ou c'est l'adresse de la fonction comparepNoeuds ?

Je n'ai encore jamais utilisé de pointeurs ou de références vers des fonctions.

c'est l'adresse de la fonction comparepNoeuds
normalement, tu aussi faire le predicat (foncteur qui retourne un bool) comme cela
Code:

1 2 3 4 5 6 7 struct comparepNoeuds { bool operator() (const Noeud * n1, const Noeud * n2) {...} }; std::multiset<Noeud*, comparepNoeuds>
04/12/2007, 17h59
Pacorabanix

Citation:

Envoyé par Mongaulois

??comment ca il n'as pas l'aire d'aimer?

oups je viens de voir la question.

Je disais qu'il n'a pas aimé car il ne compile pas (message d'erreur juste en dessous de la remarque : &comparepNoeuds n'est pas un argument valide apparemment)
04/12/2007, 18h08
Pacorabanix

Avec le prédicat ça marche très bien, merci beaucoup à toi pour cet exemple de foncteur, je sais enfin ce que ça fait concrètement maintenant. (même si ça reste flou :aie: quand même)
05/12/2007, 09h09
poukill

C'est plus propre avec le prédicat... enfin c'est mon avis... ;)
05/12/2007, 09h33
yan

Citation:

Envoyé par poukill

C'est plus propre avec le prédicat... enfin c'est mon avis... ;)

ouaip et je l'ai compris hier :aie:

Code:

1 2 3 4 5 bool ComparepNoeud(const Noeud * n1, const Noeud * n2) {...} (...) std::set<Noeud*, &ComparepNoeud> maListe;
voila juste pour info je remet juste un post pour dire qu'il semblerai que ce soit cette syntaxe à utiliser plutot que celle ci-dessus, si on veut utiliser un prédicat en temps que fonction et non foncteur :
Code:

1 2 3 4 5 6 bool ComparepNoeuds(const Noeud * n1, const Noeud * n2) {...} ... std::set<Noeud*, bool(*)(const Noeud*, const Noeud*)> maListe(ComparepNoeud);