std::set

"Nicolas Aunai" <nicolas.aunai@free.fr> a écrit dans le message de
news:mesnews.64bf7d42.93eb6e1a.119.1437@free.fr...

salut,

je suis en train d'apprendre les conteneurs de la stl, et dans quel cas
utiliser l'un plutôt que l'autre... j'ai un petit problème a vous
soumettre.

Disons que j'ai un objet A qui contient un string et un ensemble
ordonné de pointeurs sur des objets A.

pour cet ensemble ordonné, j'utilise std::set, qui me permet d'ajouter
des éléments qui sont inséré directement au bon endroit selon la
relation d'ordre définie pour A.

maintenant j'ai quelques problèmes :

class MaString
{
public:
string s;
set<const MaString *> tab;


MaString(const string &str);
void MiseAJour(const vector<MaString> &);
static void maj(vector<MaString> &);
bool operator<(const MaString &ms) const;
friend ostream & operator<<(ostream &os,const MaString &ms);
};

le vector<MaString> pris en argument par MiseAjour contient tout un tas
d'objet MaString non ordonnés, dont l'objet en cours lui même, et le
set de l'objet, doit se remplir avec les pointeurs vers les autres
objets du vector, sauf bien sûr le pointeur sur lui même. Et les
pointeurs doivent etre rangés selon la relation d'ordre de MaString.

(la relation d'ordre de MaString est tout simplement l'opérateur '<' de
son membre string)

j'ai essayé ceci :

void
MaString::MiseAJour(const vector<MaString> &s)
{
vector<MaString>::const_iterator iter_s = s.begin();

while(iter_s != s.end())
{
if(&*iter_s != this)
tab.insert(&*iter_s);
}
}


je n'ai pas l'impression que ça marche correctement, de plus, la
méthode 'insert' doit renvoyer un objet 'pair<iterator,bool>' indiquant
si l'insertion a bien eu lieu, si j'ai bien compris. Mais je pige pas
trop ce qu'est cet objet, ni comment le déclarer pour vérifier le
retour de insert.

une pair est tout simplement une structure contenant deux membres : first
(du 1er type) et second (du second type).
Par ex :
std::pair< std::vector<MaString>::iterator, bool> P tab.insert(&(*iter_s));
if(P.second)
// c'est bon, P.first référence l'élement ajouté
else
// c'est pas bon.

maintenant autre question, les set ne disposent pas de l'opérateur []
pour accéder a un de leurs membres, ou alors j'ai pas vu pas
compris...? donc le moyen pour aller sur un objet d'un set et
l'iterateur... je m'en sert pour ma surcharge d'affichage de mon objet
MaString, mais apparement j'ai une faute sur l'iterator, et je
comprends pas

si tu nous donnais le message d'erreur du compilo (si erreur à la compil) ou
ce qui se passe (si erreur à l'execution) ça nous gagnerait du temps ;-)

ostream &
operator<<(ostream &os,const MaString &ms)
{
set<const MaString*>::const_iterator i = ms.tab.begin();

os << "String = " << ms.s << endl << endl;

os << "Mes Voisins ( "<< ms.tab.size() << " ): " << endl;
os << "============= " << endl << endl;

while(i != ms.tab.end())
{
os << " - "<< *i->s << endl;
i ++;
}
os << endl;

return os;
}

--
Nico,
http://astrosurf.com/nicoastro
messenger : nicolas_aunai@hotmail.com

si tu nous donnais le message d'erreur du compilo (si erreur à la compil) ou
ce qui se passe (si erreur à l'execution) ça nous gagnerait du temps ;-)

désolé l'erreur se situe à cette ligne :

os << " - "<< *i->s << endl;

et le compilo dit :

In function
`std::ostream& operator<<(std::ostream&, const MaString&)':

SansNom1.cpp:37: request for member `
s' in `*(&i)->std::_Rb_tree_iterator<_Val, _Ref, _Ptr>::operator->()
const

[with _Val = const MaString*, _Ref = const MaString* const&, _Ptr =
const
MaString* const*]()',

which is of non-aggregate type `const MaString*'



comprends pas :/

--
Nico,
http://astrosurf.com/nicoastro
messenger : nicolas_aunai@hotmail.com

Il se trouve que Nicolas Aunai a formulé :

désolé l'erreur se situe à cette ligne :

os << " - "<< *i->s << endl;

c'est bon j'ai trouvé, bête erreur de priorité d'opérateurs...

écrire (*i)->s fonctionne très bien !

a+

--
Nico,
http://astrosurf.com/nicoastro
messenger : nicolas_aunai@hotmail.com

ah oui, mon set étant un ensemble de pointeur sur des objets perso, il
est stupide de vouloir trier des pointeurs par triage des adresses,
comment faire en sorte que le trie se fasse par rapport aux objets
pointés ?

--
Nico,
http://astrosurf.com/nicoastro
messenger : nicolas_aunai@hotmail.com

Nicolas Aunai wrote:

ah oui, mon set étant un ensemble de pointeur sur des objets perso, il
est stupide de vouloir trier des pointeurs par triage des adresses,
comment faire en sorte que le trie se fasse par rapport aux objets
pointés ?

Le template set possède un paramètre facultatif qui permet d'indiquer

comment comparer les éléments de ton set deux à deux.

--
Loïc

Alexandre wrote:

"Nicolas Aunai" <nicolas.aunai@free.fr> a écrit dans le message de
[...]

j'ai essayé ceci :

void
MaString::MiseAJour(const vector<MaString> &s)
{
vector<MaString>::const_iterator iter_s = s.begin();

while(iter_s != s.end())
{
if(&*iter_s != this)
tab.insert(&*iter_s);
}
}


je n'ai pas l'impression que ça marche correctement,
Il ne manquerait pas un '++iter_s' quelque part par hasard ?

La forme "canonique" de cette boucle serait
for(vector<MaString>::const_iterator iter_s = s.begin(); iter_s != s.end(); ++iter_s)
if(&*iter_s != this)
tab.insert(&*iter_s);

de plus, la
méthode 'insert' doit renvoyer un objet 'pair<iterator,bool>' indiquant
si l'insertion a bien eu lieu, si j'ai bien compris. Mais je pige pas
trop ce qu'est cet objet, ni comment le déclarer pour vérifier le
retour de insert.

une pair est tout simplement une structure contenant deux membres : first
(du 1er type) et second (du second type).
Par ex :
std::pair< std::vector<MaString>::iterator, bool> P > tab.insert(&(*iter_s));
if(P.second)
// c'est bon, P.first référence l'élement ajouté
else
// c'est pas bon.
Si 'P.second' vaut 'false', c'est que l'élément qu'on voulait insérer

était déjà dedans, et dans ce cas 'P.first' pointe sur cet élément.

Je ne saurais pas dire ce qui doit se passer selon la Norme si 'insert' échoue
pour d'autres raisons (genre s.size() atteint s.max_size()), mon programme
de test compilé avec gcc 3.3.1 / cygwin lève une exception std::bad_alloc
bien avant.

Falk

Loïc Joly a formulé ce vendredi :

Nicolas Aunai wrote:

ah oui, mon set étant un ensemble de pointeur sur des objets perso, il est
stupide de vouloir trier des pointeurs par triage des adresses, comment
faire en sorte que le trie se fasse par rapport aux objets pointés ?

Le template set possède un paramètre facultatif qui permet d'indiquer comment

comparer les éléments de ton set deux à deux.

en effet, j'ai vu ça... j'ai fait un "foncteur" qui compare deux objets
a partir de leur adresse. ça me trie mon set en évaluant l'élément a
insérer par rapport aux autre.

cependant, ce que je veux faire est quelque peut différent.

class A
{

set<const A*> s;
}

chaque adresse à ajouter dans le set de A, doit être comparée aux
autres selon une relation d'ordre qui prend en compte l'objet courant.

c'est comme si je voulais entrer dans le set, une série de pointeurs
vers des points, du points le plus proche de l'objet courant, au points
le plus éloigné.

class ComparePointeur
{
public:
bool operator()(const A *a1,const A *a2){return ??;}
};


en fait la relation d'ordre serait :

a1 < a2

si et seulement si a1 est plus proche de *this que a2 ne l'est.

--
Nico,
http://astrosurf.com/nicoastro
messenger : nicolas_aunai@hotmail.com

Nicolas Aunai wrote:

cependant, ce que je veux faire est quelque peut différent.
class A
{
set<const A*> s;
}

chaque adresse à ajouter dans le set de A, doit être comparée aux
autres selon une relation d'ordre qui prend en compte l'objet courant.

c'est comme si je voulais entrer dans le set, une série de pointeurs
vers des points, du points le plus proche de l'objet courant, au points
le plus éloigné.

class ComparePointeur
{
public:
bool operator()(const A *a1,const A *a2){return ??;}
};

en fait la relation d'ordre serait :

a1 < a2

si et seulement si a1 est plus proche de *this que a2 ne l'est.
Essaye quelque chose du genre :

_____________________________________________________
class A;

struct cmp_A
{
A const* pa;
cmp_A(A const* pa) : pa(pa) {}
bool operator()(A const* p1, A const* p2) const;
};

class A
{
std::set<A const*, cmp_A> s;
... // autres membres
public:
A() : s(cmp_A(this)) { ... }
void insert(A const* pa) { s.insert(pa); } // ???
};

int distance(A const& a1, A const& a2) // ou type de résultat plus approprié (double ?)
{
return ...;
}

bool cmp_A::operator()(A const* p1, A const* p2) const
{
return distance(*pa, *p1) < distance(*pa, *p2);
}
______________________________________________________

Il faut cependant faire attention au cas où deux points différents a1, a2
ont la même distance à '*this' - dans ce cas, ils seront considérés comme
équivalents par 'std::set', donc il n'en gardera qu'un seul.
Si ce n'est pas ce que tu veux, il faut plutôt utiliser std::multiset.

Falk

Falk Tannhäuser a utilisé son clavier pour écrire :

Essaye quelque chose du genre :
_____________________________________________________
class A;

struct cmp_A
{
A const* pa;
cmp_A(A const* pa) : pa(pa) {}
bool operator()(A const* p1, A const* p2) const;
};

class A
{
std::set<A const*, cmp_A> s;
... // autres membres
public:
A() : s(cmp_A(this)) { ... }
void insert(A const* pa) { s.insert(pa); } // ???
};

int distance(A const& a1, A const& a2) // ou type de résultat plus approprié
(double ?) {
return ...;
}

bool cmp_A::operator()(A const* p1, A const* p2) const
{
return distance(*pa, *p1) < distance(*pa, *p2);
}
______________________________________________________

et cette insertion triée dans le set, ça marche pour n éléments ?
nan parce que... j'ai un comportement TRES bizarre sur un programme,
que je ne comprends vraiment pas...

voici l'explication du probleme :

j'ai mon vector d'objets qui contient n objets.
chaque objet a son set de pointeurs sur les n-1 autres objets, triés
selon la relation d'ordre.

dans la théorie ça marche, le probleme survient lorsque n>=4


j'explique en détail :

pour n=2, chaque objet a dans son set UN seul pointeur, pas de pb...

pour n=3, chaque objet a dans son set, DEUX pointeurs, le second est
inséré en comparaison avec le premier selon la relation d'ordre... et
mon set est convenablement trié...


par contre, pour n=4 là commencent les ennuis...
en effet, alors que mes deux premiers pointeurs étaient bien insérés
l'un par raport a l'autre, le 3eme pointeur s'insère apparement
systématiquement mal (au début du set semble-t-il)

bref je comprends pas, ça doit etre moi qui me sert mal de la fonction
insert.


voici un peu de copier/collé de l'execution pour illustrer un peu ce
que je dis :

pour n=3 objets (Cluster) dans le vector (Systeme)

cluster 0 :
======================================= Position : [ 1, 2, 3 ]
Mes influences :
----------------
-Position : [ 1, 2, 3.5 ] D = 0.5
-Position : [ 1, 2, 4.1 ] D = 1.1
========================================
cluster 1 :
======================================= Position : [ 1, 2, 4.1 ]
Mes influences :
----------------
-Position : [ 1, 2, 3.5 ] D = 0.6
-Position : [ 1, 2, 3 ] D = 1.1
========================================
cluster 2 :
======================================= Position : [ 1, 2, 3.5 ]
Mes fils :
----------
Mes influences :
----------------
-Position : [ 1, 2, 3 ] D = 0.5
-Position : [ 1, 2, 4.1 ] D = 0.6
========================================


vous voyez que les set qui sont les influences, sont correctement triés
par distance croissante des autres points du systeme.


maintenant si j'insère un autre point :

cluster 0 :
======================================= Position : [ 1, 2, 3 ]
Mes influences :
----------------
-Position : [ 1, 10, 10 ] D = 10.63
-Position : [ 1, 2, 4.1 ] D = 1.1
-Position : [ 1, 2, 3.5 ] D = 0.5
========================================

cluster 1 :
======================================= Position : [ 1, 2, 4.1 ]
Mes influences :
----------------
-Position : [ 1, 10, 10 ] D = 9.94
-Position : [ 1, 2, 3.5 ] D = 0.6
-Position : [ 1, 2, 3 ] D = 1.1
========================================

cluster 2 :
======================================= Position : [ 1, 2, 3.5 ]
Mes influences :
----------------
-Position : [ 1, 10, 10 ] D = 10.31
-Position : [ 1, 2, 4.1 ] D = 0.6
-Position : [ 1, 2, 3 ] D = 0.5
========================================

cluster 3 :
======================================= Position : [ 1, 10, 10 ]
Mes influences :
----------------
-Position : [ 1, 2, 4.1 ] D = 9.94
-Position : [ 1, 2, 3.5 ] D = 10.31
-Position : [ 1, 2, 3 ] D = 10.63
========================================

systématiquement le point rajouté (1,2,4.1) se place mal dans le set.

ma fonction d'insertion est :

void
Cluster::maj_influences(const vector<Cluster> &t)
{
vector<Cluster>::const_iterator i = t.begin();
Influences.clear(); //efface les influences pour refaire...

pair<set<const Cluster*>::iterator,bool> p;
p.second = true;

while(i != t.end() && p.second)
{
if(&*i != this)
p = Influences.insert(&*i);//devrait insérer au bon endroit
i ++;
}
}


voila, si vous pouvez trouver ce qui va pas... moi je sèche
complètement


a+ et merci d'avance

--
Nico,
http://astrosurf.com/nicoastro
messenger : nicolas_aunai@hotmail.com

Nicolas Aunai <nicolas.aunai@free.fr> écrivait:

voici l'explication du probleme :

C'est un peu confus.

pair<set<const Cluster*>::iterator,bool> p;
[...]
p = Influences.insert(&*i);//devrait insérer au bon endroit

Comme p est utilisé comme resultat de Influences.insert j'en déduis
que le type de Influences -- ou un de ses types de base -- est
set<const Cluster*>. Il suit que le tri est fait avec std::less< const
Cluster* >::operator() qui, par défaut, va ordonner les pointeurs.

La solution n'est pas évidente car tu veux trier les "influences" d'un
cluster, la référence, fonction de la distance Euclidienne des
positions absolues des autres clusters. Donc l'opérateur de tri :

inline bool
std::less< const Cluster* >::operator()(
Cluster const * lhs,
Cluster const * rhs) const;

doit connaître la position absolue de la référence.

--
Franck Branjonneau <fasbjx@free.fr>