STL set contenant des pointeurs

Frédéric Mayot wrote:

Bonjour,

Voici mon problème :

J'ai une collection d'instances d'une classe A qui contient un membre
string appelé M.

Je veux conserver cette collection de manière triée, donc un set<A*> me
semblait être une bonne idée pourvu que je définisse un foncteur pour
comparer mes pointeurs.

Je suppose que la comparaison se fait en fait sur la chaine M contenue
dans A.

Pour l'insertion et le parcours total, pas de problème. Maintenant, et
vous vous en douterez, si je veux connaître l'existence d'un nom dans
ma collection, je souhaiterais que cela se fasse sans parcourir l'arbre
intégralement (mais plutôt en profitant de la structure de l'arbre rouge
et noir). Mais là, je suis coincé...

A* bidon = new A(....);
bidon->M = "Toto";
if (mySet.find(bidon) != mySet.end())
// Trouvé

Y a-t-il une autre solution que de dupliquer M en l'utilisant un
map<string, A*> ?

Utiliser un map<string, A*> (en enlevant éventuellement la donnée M de
A) dès le début ?

--
Loïc

On Tue, 28 Oct 2003 23:43:13 +0100, Frédéric Mayot <toto@toto.com>
wrote:

J'ai une collection d'instances d'une classe A qui contient un membre
string appelé M.

Je veux conserver cette collection de manière triée, donc un set<A*> me
semblait être une bonne idée

Pourquoi pas un set<A*> ?

pourvu que je définisse un foncteur pour
comparer mes pointeurs.

Si tu gardes ton idée de pointeurs, inutile de définir un foncteur,
std::less<A*> devrait convenir.

Maintenant, et
vous vous en douterez, si je veux connaître l'existence d'un nom dans
ma collection, je souhaiterais que cela se fasse sans parcourir l'arbre
intégralement

Une solution, en se basant sur set<A>, est de définir le foncteur de
comparaison de façon à favoriser la clé -- ce qui revient un peu à
réinventer map<>, mais bon...

class Machin;

class A
{
std::string m;
Machin autres_donnees;
};

struct Compare_A
{
bool operator() (A const& a1, A const& a2) const
{
return a1.m < a2.m;
}
};


Un "std::set <A, Compare_A>" est à peu près équivalent à un "std::map
<std::string, Machin>".

Pour trouver un A ayant un membre m donné, il suffit de créer un A
avec ce m, et d'utiliser std::set<>::lower_bound.



Autre version :

struct Compare_A
{
bool operator() (A const& a1, A const& a2) const
{
if (a1.m == a2.m)
{
return a1.autres_donnees < a2.autres_donnees;
}
else
{
return a1.m < a2.m;
}
}
};


Un "std::set <A, Compare_A>" est alors à peu près équivalent à un
"std::multimap <std::string, Machin>".



--
;-)

En fait, c'est pas bête comme astuce mais ça fait un peu crade, non ?
Si mon objet A est énorme et lourd à construire et que j'ai à chercher
plein de choses, ça risque de ne pas convenir...

Pour pallier au problème, on peut peut-être faire en sorte que A dérive
d'une classe vide Base, faire un set<Base*> et créer les instances
fictives en tant que Base. Mais bon, là c'est le DP Gaz Factory ;-)

Merci quand même.

Une autre idée peut-être ?


Loïc Joly wrote:

Frédéric Mayot wrote:

Bonjour,

Voici mon problème :

J'ai une collection d'instances d'une classe A qui contient un membre
string appelé M.

Je veux conserver cette collection de manière triée, donc un set<A*>
me semblait être une bonne idée pourvu que je définisse un foncteur
pour comparer mes pointeurs.

Je suppose que la comparaison se fait en fait sur la chaine M contenue
dans A.

Pour l'insertion et le parcours total, pas de problème. Maintenant, et
vous vous en douterez, si je veux connaître l'existence d'un nom dans
ma collection, je souhaiterais que cela se fasse sans parcourir
l'arbre intégralement (mais plutôt en profitant de la structure de
l'arbre rouge et noir). Mais là, je suis coincé...

A* bidon = new A(....);
bidon->M = "Toto";
if (mySet.find(bidon) != mySet.end())
// Trouvé

Y a-t-il une autre solution que de dupliquer M en l'utilisant un
map<string, A*> ?

Utiliser un map<string, A*> (en enlevant éventuellement la donnée M de
A) dès le début ?

Une solution, en se basant sur set<A>,est de définir le foncteur de
comparaison de façon à favoriser la clé

Ca, j'y avais déjà pensé... Je tiens vraiment à ne stoquer que mes
adresses dans cet ensemble, pas mes instances.

-- ce qui revient un peu à
réinventer map<>, mais bon...

J'ai pas l'impression, parce que dans ce cas, on ne duplique pas l'objet
string...

Pour trouver un A ayant un membre m donné, il suffit de créer un A
avec ce m, et d'utiliser std::set<>::lower_bound.

Je pense que le problème est le même qu'avec la solution de Loîc (cf.
mon post).

Fred

On Wed, 29 Oct 2003 00:28:00 +0100, Frédéric Mayot <toto@toto.com>
wrote:

Je tiens vraiment à ne stoquer que mes
adresses dans cet ensemble, pas mes instances.

Libre à toi, si tu sais vraiment ce que tu fais.

Dans ce cas, la solution est à peu près la même, sauf qu'il faut jouer
avec les indirections :

struct Compare_A_ptr
{
bool operator() (A* a1, A* a2) const
{
return a1->m < a2->m;
}
};

et

std::set <A*, Compare_A_ptr>

Je pense que le problème est le même qu'avec la solution de Loîc (cf.
mon post).

Malheureusement, je ne peux pas le lire, car tu l'as écrit à l'envers
-- cf <http://www.giromini.org/usenet-fr/repondre.html>.

--
;-)

On Wed, 29 Oct 2003 00:28:00 +0100, Frédéric Mayot <toto@toto.com>
wrote:

Je tiens vraiment à ne stoquer que mes
adresses dans cet ensemble, pas mes instances.

Libre à toi, si tu sais vraiment ce que tu fais

Dans ce cas, la solution est à peu près la même, sauf qu'il faut jouer
avec les indirections :

struct Compare_A_ptr
{
bool operator() (A* a1, A* a2) const
{
return a1->m < a2->m;
}
};

et

std::set <A*, Compare_A_ptr>

Au fait, combien d'éléments y a-t-il dans le set<>, et combien de
recherches dois-tu faire ? S'il n'y a que quelques milliers
d'éléments, tu devrais tenter une solution "naïve" et simple, et ne
chercher une solution plus performante que si le profiler en indique
un besoin réel.

Je pense que le problème est le même qu'avec la solution de Loîc (cf.
mon post).

Malheureusement, je ne peux pas lire ton post, car tu l'as écrit à
l'envers -- cf <http://www.giromini.org/usenet-fr/repondre.html>.

--
;-)

En fait, c'est pas bête comme astuce mais ça fait un peu crade, non ?
Si mon objet A est énorme et lourd à construire et que j'ai à chercher
plein de choses, ça risque de ne pas convenir...

Pour pallier au problème, on peut peut-être faire en sorte que A dérive
d'une classe vide Base, faire un set<Base*> et créer les instances
fictives en tant que Base. Mais bon, là c'est le DP Gaz Factory

Merci quand même.

Une autre idée peut-être ?

Dans ce cas, la solution est à peu près la même, sauf qu'il faut jouer
avec les indirections :

struct Compare_A_ptr
{
bool operator() (A* a1, A* a2) const
{
return a1->m < a2->m;
}
};

et

std::set <A*, Compare_A_ptr>

Oui, ça je l'ai bien compris, mais ce qui me gêne c'est d'avoir à créer
une instance de A pour pouvoir faire ma recherche... Je vais quand même
pas faire un copier/coller de stl_tree.h pour pouvoir ajouter une
méthode bool find (string)...

Au fait, combien d'éléments y a-t-il dans le set<>, et combien de
recherches dois-tu faire ? S'il n'y a que quelques milliers
d'éléments, tu devrais tenter une solution "naïve" et simple, et ne
chercher une solution plus performante que si le profiler en indique
un besoin réel.

C'est une application fictive, donc on peut imaginer qu'il y en aura
beaucoup. L'objectif du set est de maintenir un tri, pas de faire des
recherches de doublons qui seront occasionnelles. J'aurai une
hash_map<uid, A*> (typedef int uid) pour un accès direct (chaque
instance de A possède un identifiant unique pour faciliter les saisies
utilisateur).

Malheureusement, je ne peux pas lire ton post, car tu l'as écrit à
l'envers -- cf <http://www.giromini.org/usenet-fr/repondre.html>.

Je reposte.

Dans ce cas, la solution est à peu près la même, sauf qu'il faut jouer
avec les indirections :

struct Compare_A_ptr
{
bool operator() (A* a1, A* a2) const
{
return a1->m < a2->m;
}
};

et
std::set <A*, Compare_A_ptr>

Oui, ça je l'ai bien compris, mais ce qui me gêne c'est d'avoir à créer
une instance de A pour pouvoir faire ma recherche... Je vais quand même
pas faire un copier/coller de stl_tree.h pour pouvoir ajouter une
méthode bool find (string)...

Au fait, combien d'éléments y a-t-il dans le set<>, et combien de
recherches dois-tu faire ? S'il n'y a que quelques milliers
d'éléments, tu devrais tenter une solution "naïve" et simple, et ne
chercher une solution plus performante que si le profiler en indique
un besoin réel.

C'est une application fictive, donc on peut imaginer qu'il y en aura
beaucoup. L'objectif du set est de maintenir un tri, pas de faire des
recherches de doublons qui seront occasionnelles. J'aurai une
hash_map<uid, A*> (typedef int uid) pour un accès direct (chaque
instance de A possède un identifiant unique pour faciliter les saisies
utilisateur).

Malheureusement, je ne peux pas lire ton post, car tu l'as écrit à
l'envers -- cf <http://www.giromini.org/usenet-fr/repondre.html>.

Je reposte.

Loïc Joly <loic.actarus.joly@wanadoo.fr> wrote in message news:<bnmsn2$c05$1@news-reader2.wanadoo.fr>...

Frédéric Mayot wrote:

A* bidon = new A(....);
bidon->M = "Toto";
if (mySet.find(bidon) != mySet.end())
// Trouvé

Tu ne voulais pas plutôt dire:
A bidon;
bidon.M = "Toto";
if (mySet.find(&bidon) != mySet.end())
// Trouvé

Bertrand.