Logo GNT
Actualités Tests & Guides Bons Plans
Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11
Entraide Développement Développement Langage C++ problème de parcours de map

problème de parcours de map

24 réponses
Avatar
MGN
Bonsoir,
J'ai des map du type
std::map<objet*,objet*,foncteur>
où le foncteur varie (le type des objets aussi, mais ça ne change rien à la
définition de la map).
Je cherche à parcourir (uniquement parcourir, pas modifier) une map de ce
type sans connaître le foncteur qui a été utilisé pour le tri, ie quelque
chose du type :

std::map<objet*,objet*,foncteur> x;
std::map<objet*,objet*>::iterator it;
for(it=x.begin();it!=x.end();++it) {}

Evidement, cette syntaxe ne marche pas. Quelqu'un sait comment faire ?
Merci à vous
Marc
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2 3
Avatar
James Kanze
On Sep 10, 4:19 pm, "MGN" wrote:
> La solution de James Kanze: les types sont les mêmes, seule
> l'initialisation de la fonction de comparaison change.



bon, je suis un peu neuneu (j'utilise toujours des foncteurs
en fait) => Je voudrais savoir si c'est bien comme ça qu'il
faut procéder :



bool ordre_croissant(int* a,int* b) { return *a<*b; }
bool ordre_decroissant(int* a,int* b) { return *b<*a; }



std::map<int*,std::string*,bool(*)(int*,int*)> x;
x.comp=ordre_decroissant;



Plutôt :
typedef std::map< int*, std::string*, bool (*)( int*, int* ) >
Map ;
Map x( ordre_croissant ) ;
Il faut donner la fonction de comparaison lors de la
construction, et on ne peut pas la changer par la suite (pour
des raisons évidentes).

Et en passant, c'est fortement suspect, tous ces pointeurs. Dans
la pratique, on n'a des pointeurs à des int ou à des std::string
que dans le cas où le pointeur pourrait être nul, et on n'en
alloue jamais dynamiquement.

x[new int(0)]=new std::string("zéro");
x[new int(1)]=new std::string("un");
x[new int(2)]=new std::string("deux");



Ma question : y-a-t-il un moyen de lier la fonction de
comparaison à x lors de la déclaration de x ?



Il n'y a pas de façon à en faire autrement. Comment veux-tu que
fonctionne un map si sa fonction de comparaison puisse changer à
n'importe quel instant ?

--
James Kanze
Avatar
MGN
> Plutôt :
typedef std::map< int*, std::string*, bool (*)( int*, int* ) >
Map ;
Map x( ordre_croissant ) ;
Il faut donner la fonction de comparaison lors de la
construction, et on ne peut pas la changer par la suite (pour
des raisons évidentes).



ok, merci.
Oui, je sais bien que ça n'a pas de sens de changer la fonction de
comparaison...
Bon, j'ai un problème avec mon implémentation de la stl. Je m'explique :

template<typename T>
bool ordre(int* a,int* b) { return *a<*b; }

1) si je fais
typedef std::map<int*,string*, bool(*)(int*,int*)> MapType;
MapType x(ordre<bool>);
j'ai le message :
Impossible de trouver une correspondance pour 'map<int *,string *,bool
(*)(int *,int *),allocator<pair<int * const,string *> > >::map(bool (*)(int
*,int *))'

2) si je fais
typedef std::map<int*,string*, bool(*)(int*,int*)> MapType;
MapType x;
x.comp=ordre<bool>;

ça marche. En plus, par la suite, je peux changer x.comp ! (mais ça ne
retrie pas la map)

Tu vois pourquoi ?
nota : ne te pose pas de question sur le "sens" du code, c'est juste pour
l'exemple...
Merci en tous cas pour tes réponses précieuses...
Marc
Avatar
MGN
je crois comprendre pourquoi...
dans le premier cas, le pointeur de fonction est un temporaire...
Il faut que j'écrive avant par exemple :

typedef bool(*comp)(int*,int*);
comp f=ordre<bool>;
et ça marche.

C'est çà ?

Mais bon, je suis étonné de pouvoir changer a posteriori la propriété comp
de map
Bonne nuit à ceux qui dorment.
Avatar
Fabien LE LEZ
On Thu, 10 Sep 2009 00:50:32 +0200, "MGN" :

J'ai des map du type
std::map<objet*,objet*,foncteur>
où le foncteur varie



Es-tu sûr que map<> soit le conteneur adapté dans ton cas ?
La caractéristique principale de map<>, c'est que les données sont
triées en permanence. C'est coûteux, et pas toujours nécessaire.

Dans pas mal de cas, on a juste besoin que le conteneur soit trié à la
fin, après qu'on l'ait rempli. Auquel cas un vector<pair<>> convient
aussi bien (ou peut-être list ou deque, suivant les cas).

L'avantage : tu peux trier plusieurs fois, avec des ordres différents.

Si tu as besoin d'un conteneur associatif constant (i.e. on remplit le
conteneur, puis on lit/trie/etc.), tu peux encapsuler un vector<> et
une recherche dichotomique.
Avatar
MGN
"Fabien LE LEZ" a écrit dans le message de
news:
On Thu, 10 Sep 2009 00:50:32 +0200, "MGN" :

J'ai des map du type
std::map<objet*,objet*,foncteur>
où le foncteur varie



Es-tu sûr que map<> soit le conteneur adapté dans ton cas ?


oui, je suis sûr, j'accède aux valeurs à partir d'une clé, qui doit être
unique.

Si tu as besoin d'un conteneur associatif constant (i.e. on remplit le
conteneur, puis on lit/trie/etc.), tu peux encapsuler un vector<> et
une recherche dichotomique.


le contenu peut être modifié à tout moment

Mais je te remercie de tes suggestions intéressantes.
Marc
Avatar
Michael Doubez
On 11 sep, 00:09, "MGN" wrote:
je crois comprendre pourquoi...
dans le premier cas, le pointeur de fonction est un temporaire...
Il faut que j'écrive avant par exemple :

typedef bool(*comp)(int*,int*);
comp f=ordre<bool>;
et ça marche.

C'est çà ?

Mais bon, je suis étonné de pouvoir changer a posteriori la proprié té comp
de map



C'est pas ce que James Kanze a dir. Il te propose simplement de faire
converger les types entre map<> utilisant des comparateurs differents.
Tu ne modifies pas le comp de la map.
Toutes tes maps auront le type
map<obj*,obj*,bool (*)(obj*,obj*)>

Mais deux map<> utiliseront un pointeur de fonction différent.
Exemple:
// clé a deux entrée
struct two_keys
{
int key_1;
int key_2;
};

typedef map<two_keys,int,bool (*)(const two_keys&,const two_keys&)>
tkmap;

// fonction less sur key_1
bool less_key_1(const two_keys&lhs,const two_keys&rhs)
{
return lhs.key_1< rhs.key_1;
}

// fonction less sur key_2
bool less_key_2(const two_keys&lhs, const two_keys&rhs)
{
return lhs.key_2 < rhs.key_2;
}

Ensuite tu peux créer les instances:
tkmap map1(less_key_1):
tkmap map2(less_key_2):

map1 et map2 ont le même type d'itérateur mais ils n'utilisent pas les
même fonctions de comparaison.

--
Michael
Avatar
James Kanze
On Sep 10, 11:50 pm, "MGN" wrote:
> Plutôt :
> typedef std::map< int*, std::string*, bool (*)( int*, int* ) >
> Map ;
> Map x( ordre_croissant ) ;
> Il faut donner la fonction de comparaison lors de la
> construction, et on ne peut pas la changer par la suite (pour
> des raisons évidentes).



Oui, je sais bien que ça n'a pas de sens de changer la fonction de
comparaison...



Ce n'est pas que ça n'a pas de sens, c'est que la norme ne
fournit même pas de moyen à le faire. Il faut impérativement que
la fonction soit fourni lors de la construction de l'objet.

Bon, j'ai un problème avec mon implémentation de la stl. Je
m'explique :



template<typename T>
bool ordre(int* a,int* b) { return *a<*b; }



Pourquoi un template ?

1) si je fais
typedef std::map<int*,string*, bool(*)(int*,int*)> MapType;
MapType x(ordre<bool>);
j'ai le message :
Impossible de trouver une correspondance pour 'map<int
*,string *,bool (*)(int *,int *),allocator<pair<int *
const,string *> > >::map(bool (*)(int *,int *))'



Ça marche chez moi (VC++). Ça a l'air d'être un problème de
compilateur (surtout en vue de tes exemples qui marchent), et
non un problème de bibliothèque ; qu'est-ce que tu utilises
comme compilateur ? (Il n'y a pas si longtemps, il y avait
encore des compilateurs qui n'acceptait pas la notation
function< type > pour la spécification du paramètre du template.
Est-ce que tu te sers d'une version assez récente du
compilateur ?)

2) si je fais
typedef std::map<int*,string*, bool(*)(int*,int*)> MapType;
MapType x;
x.comp=ordre<bool>;



ça marche.



Chez moi aussi ! Alors que ça ne doit pas marcher ; selon la
norme, la classe générique map n'a pas de membre « comp ».

En plus, par la suite, je peux changer x.comp ! (mais ça ne
retrie pas la map)



C'est effectivement le problème. Tu changes la fonction de
comparaison, et l'invariante de l'ordre dans le map se trouve
violé.

Tu vois pourquoi ?



De toutes apparences, des problèmes liés à ton implémentation.
Dans une implémentation conforme de la bibliothèque, il n'y a
pas de symbole « comp » membre de std::map. Et le compilateur
semble avoir des problèmes avec la résolution quand tu passes le
nom d'une fonction générique avec un paramètre de template
explicit.

--
James Kanze
Avatar
MGN
oui, j'avais compris en fait.
Mon problème vient plutôt d'un message d'erreur du compilateur lorsque la
fonction de tri est une fonction template.

template<typename T> bool f(int u,int v) { return u<v; }
typedef std::map<int,int,bool(*)(int,int)> Map;

si j'écris par exemple
Map x(f<bool>);
mon compilateur refuse

je dois écrire
bool(*func)(int,int)=f<bool>;
Map x(func);
pour qu'il accepte...

merci quand même de tes réponses.
Marc
Avatar
MGN
> > template<typename T>
> bool ordre(int* a,int* b) { return *a<*b; }

Pourquoi un template ?



juste pour l'exemple, ici il ne sert bien sûr à rien.

Est-ce que tu te sers d'une version assez récente du


compilateur ?)

j'utilise BCB 2007
Enfin, merci de m'avoir rassuré en m'indiquant que le problème n'est a
priori pas de moi :-()
Marc
Avatar
pjb
"MGN" writes:

"Fabien LE LEZ" a écrit dans le message de
news:
On Thu, 10 Sep 2009 00:50:32 +0200, "MGN" :

J'ai des map du type
std::map<objet*,objet*,foncteur>
où le foncteur varie



Es-tu sûr que map<> soit le conteneur adapté dans ton cas ?


oui, je suis sûr, j'accède aux valeurs à partir d'une clé, qui doit
être unique.



Donc tu n'as pas besoin de map.

Fabien a clairement expliqué que la caractéristique de map, c'est que
les entrées sont triées. D'où le paramètre compare du template.


Tu ne cite que des contraintes qui justifient seulement une table de
hashage. Mais ça n'existe pas dans la stl. Voir boost::hashtable
http://www.boost.org/doc/libs/1_35_0/doc/html/boost/intrusive/hashtable.html


--
__Pascal Bourguignon__
1 2 3