set<Pointeur*> mal trié

Version imprimable

15/12/2008, 17h27
laflak

set<Pointeur*> mal trié

Bonjour, je suis sur un projet ou je manipule une grande quantité d'objet sous forme de pointeurs.
J'aimerai donc stocker ces objets de manière triés pour pouvoir avoir une recherche rapide.
J'utilise donc le conteneur std::set que je déclare de cette manière :

Code:

set<Pointeur*> _liste;

J'ai surchargé l'opérateur < :

Code:

bool operator< (const Pointeur &a, const Pointeur &b);

Malheuresement, lorsque je parcours mon set je me rend compte que les pointeurs ne sont pas triés en fonction de la valeur de mes objets mais en fonction de la valeur de l'adresse du pointeur.

Quels sont les solutions pour obtenir une liste triée en fonction de la valeur des items et non pas en fonction de la valeur des adresses des pointeurs ?

Merci d'avance.

Pour rappel:
Code:

1 2 3 template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;
A toi de lui fournir une classe Compare qui parte de Pointeur*.

15/12/2008, 17h58
laflak

ok je teste ça.
Si tu as un lien d'exemple d'implémentation sur internet, c'est bien venu.

Merci beaucoup.
15/12/2008, 18h35
loufoque

Puis-je savoir pourquoi tu utilises des pointeurs ?
15/12/2008, 20h42
laflak

je suis en train de prog une structure VEF : vertex edge face pour pouvoir travailler sur un maillage 3D.

J'utilise des pointeurs car je créer par exemple un Vertex et que ensuite je fais avoir des liens vers ce vertex depuis mes edges et mes faces. Mes edges auront un lien vers ses vertex et ces faces. Les faces auront un lien vers leurs edges et leurs vertex.
16/12/2008, 04h22
laflak

Je comprend pas trop comment je dois implémenter ça.

En fait je dois faire quoi je dois dériver Pointeur* pour obtenir un classe ou je surcharge l'opérateur < ?

Après un peu de recherche j'en suis la :

vertex.hpp :

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
 
#ifndef VERTEX_HPP
#define VERTEX_HPP
 
class Vertex {
 
public:
  // Constructeur
  Vertex (double x, double y, double z);
  // Accesseur
  const double &x() const;
  const double &y() const;
  const double &z() const;
 
private:
  double _x, _y, _z;
};
 
//Opérateur de comparaison
bool operator== (Vertex &a, Vertex &b);
bool operator!= (Vertex &a, Vertex &b);
bool operator>= (Vertex &a, Vertex &b);
bool operator<= (Vertex &a, Vertex &b);
bool operator>  (Vertex &a, Vertex &b);
bool operator<  (Vertex &a, Vertex &b);
 
#endif /* VERTEX_HPP */

foncteur_vertex.hpp :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
#ifndef FONCTEUR_VERTEX_HPP
#define FONCTEUR_VERTEX_HPP
 
#include "vertex.hpp"
 
class FoncteurVertex {
public:
  bool operator() (const Vertex *a, const Vertex *b) const;
};
 
#endif /* FONCTEUR_VERTEX_HPP */

main.cpp

Code:

1
2
 
set<Vertex*, FoncteurVertex> _vertex;

Mais voila j'ai un problème à la compilation :

Code:

1
2
 
erreur: invalid initialization of reference of type ‘const std::set<Vertex*, std::less<Vertex*>, std::allocator<Vertex*> >&’ from expression of type ‘const std::set<Vertex*, FoncteurVertex, std::allocator<Vertex*> >’

Je comprend pas trop les foncteur c'est tout nouveau pour moi et je trouve plus trop de docmuentation sur internet.

Merci d'avance.

16/12/2008, 07h14
laflak
j'ai pas le temps de l'implémenter dans la matinée mais cet aprem ou ce soir je tente d'implémenter :
Code:

1 2 template<class T> class FunctorPointerSet
Vu l'erreur c peut etre ca.

Chez moi, ça compile sous VC++Express et gcc:

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
 
#include <set>
class Vertex {
 
public:
  // Constructeur
  Vertex (double x, double y, double z);
  // Accesseur
  const double &x() const;
  const double &y() const;
  const double &z() const;
 
private:
  double _x, _y, _z;
};
 
//Opérateur de comparaison
bool operator== (Vertex &a, Vertex &b);
bool operator!= (Vertex &a, Vertex &b);
bool operator>= (Vertex &a, Vertex &b);
bool operator<= (Vertex &a, Vertex &b);
bool operator>  (Vertex &a, Vertex &b);
bool operator<  (Vertex &a, Vertex &b);
 
class FoncteurVertex {
public:
  bool operator() (const Vertex *a, const Vertex *b) const;
};
 
int main(int, char)
{
 
   std::set<Vertex*,FoncteurVertex> mon_ensemble;
 
	return 0;
}

En toute logique, tes surcharges des opérateurs devraient plus ressembler à :

Code:

bool operator== (Vertex const &a, Vertex const &b);

Citation:
Envoyé par laflak
Mais voila j'ai un problème à la compilation :
Code:

1 2 erreur: invalid initialization of reference of type ‘const std::set<Vertex*, std::less<Vertex*>, std::allocator<Vertex*> >&’ from expression of type ‘const std::set<Vertex*, FoncteurVertex, std::allocator<Vertex*> >’
J'ai l'impression que dans ton code, tu mélange des set<Vertex *> et des set<Vertex*, FoncteurVertex>, qui sont deux types différents.

PS : Le nommage de FoncteurVertex n'est pas très indicatif. Un truc genre CompareVertexPointer me semblerait plus clair. Il est de plus possible d'écrire un tel foncteur qui marche pour tout type de pointeur, pas seulement des pointeurs sur Vertex (je me demande s'il n'y en a pas un tout fait dans boost, mais autrement, c'est assez simple).

16/12/2008, 21h41
laflak

J'ai rajouté les const pour mes opérateurs surchargés et je suis en train de regarder pour implémenter mon template fonctor.
17/12/2008, 08h55
3DArchi

Penses à :resolu: quand ton problème le sera :mrgreen:

bon j'ai continué à tester d'autre truc je pense que je touche au but mais j'ai encore un petit bug.

Dans mon main :
Code:

1 2 set<Vertex*, SortVertex> _vertex;
Dans comparePointeur.hpp :
Code:

1 2 3 4 5 6 struct SortVertex { bool operator()(Vertex *a, Vertex *b) { return ((*a) < (*b)); } };
Mon message d'erreur à la compilation :
Code:

1 2 erreur: invalid initialization of reference of type ‘const std::set<Vertex*, std::less<Vertex*>, std::allocator<Vertex*> >&’ from expression of type ‘const std::set<Vertex*, SortVertex, std::allocator<Vertex*> >’
Donc voila doit y avoir une ou deux petite modification à faire sur ma structure, je continue à chercher, mais si quelqu'un à la solution ca me ferais plaisir ca fait trop longtemps que je suis sur ces quelque ligne de code.

Merci d'avance.

On m'as passé un code qui marche nikel, mais avec des pointeurs d'entiers :

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
 
#include <iostream>
#include <set>
#include <string>
 
#include <boost/foreach.hpp>
 
class A
{
public:
    A(int i_ = 0)
     : i(i_)
    {}
 
    int get_i() const { return i;}
 
private:
    int i;
};
 
class Foncteur
{
public:
    bool operator()(const A* a, const A* b)
    {
        return a->get_i() < b->get_i();
    }
};
 
int main()
{
    std::set<A*, Foncteur> myset;
 
    myset.insert(new A(5));
    myset.insert(new A(-2));
    myset.insert(new A(87));
    myset.insert(new A(-1));
 
    BOOST_FOREACH(A* ptr, myset)
        std::cout << ptr->get_i() << '\n';
 
    return 0;
}

Malheureusement quand je l'adapte à mon code ca me fait :

Code:

1
2
 
erreur: invalid initialization of reference of type ‘const std::set<Face*, std::less<Face*>, std::allocator<Face*> >&’ from expression of type ‘const std::set<Face*, SortFace, std::allocator<Face*> >’

Mon code :

Code:

1
2
3
4
5
6
7
8
9
10
 
class SortVertex {
public:
  bool operator()(const Vertex *a, const Vertex *b) {
    return ((*a) < (*b));
  }
};
 
 
set<Vertex*, SortVertex> _vertex;

21/12/2008, 23h31
Laurent Gomila

Ce serait plus facile si tu nous montrais ton code. Visiblement tu as toujours le même problème : tu mélanges des set<Vertex*> et des set<Vertex*, SortVertex>.