Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
clé ad-hoc pour un map
23 views
Skip to first unread message
hey...@gmail.com
Sep 24, 2012, 4:55:46 AM9/24/12
to
Bonjour,
Je suis en train de travailler sur des map dont j'ai défini la clé suivante.
class MRange
{
private:
char * a;
size_t s;
public:
MRange(void * a, size_t size);
friend bool operator(const MRange &left, const MRange &right) {
return (left.a + left.s <= right.a);}
};
ça m'a tout l'air de fonctionner comme attendu, notamment deux MRange "différent" du type MRange(0x0,10) et MRange(0x1,5) sont en fait considérés comme égaux (même clé) dans le map suivant:
std::map<MRange,int> memory;
Ceci provient du fait que (et c'est là que je ne maîtrise pas trop) l'opérateur == est déduit de la définition de l'opérateur < (au moins dans le fonctionnement du map).
Ma question est donc la suivante: Que se passe-t-il si je redéfinit l'opérateur == comme ci-dessous ? Cela risque-t-il de changer l'ordre de mon map ? Et si non, est-ce garanti ?
friend bool operator==(const MRange & left, const MRange &right)
{
return ((left.a==right.a) && (left.s == right.s))
}
Merci pour vos lumières.
AG.
Je suis en train de travailler sur des map dont j'ai défini la clé suivante.
class MRange
{
private:
char * a;
size_t s;
public:
MRange(void * a, size_t size);
friend bool operator(const MRange &left, const MRange &right) {
return (left.a + left.s <= right.a);}
};
ça m'a tout l'air de fonctionner comme attendu, notamment deux MRange "différent" du type MRange(0x0,10) et MRange(0x1,5) sont en fait considérés comme égaux (même clé) dans le map suivant:
std::map<MRange,int> memory;
Ceci provient du fait que (et c'est là que je ne maîtrise pas trop) l'opérateur == est déduit de la définition de l'opérateur < (au moins dans le fonctionnement du map).
Ma question est donc la suivante: Que se passe-t-il si je redéfinit l'opérateur == comme ci-dessous ? Cela risque-t-il de changer l'ordre de mon map ? Et si non, est-ce garanti ?
friend bool operator==(const MRange & left, const MRange &right)
{
return ((left.a==right.a) && (left.s == right.s))
}
Merci pour vos lumières.
AG.
Marc Boyer
Sep 24, 2012, 7:20:14 AM9/24/12
to
Le 24-09-2012, hey...@gmail.com <hey...@gmail.com> a écrit :
> Bonjour,
>
> Je suis en train de travailler sur des map dont j'ai défini la clé suivante.
>
> class MRange
> {
> private:
> char * a;
> size_t s;
> public:
> MRange(void * a, size_t size);
> friend bool operator(const MRange &left, const MRange &right) {
> return (left.a + left.s <= right.a);}
> };
Est-ce que ce ne serait pas plutôt l'opérateur de comparaison qu'il faudrait
> Bonjour,
>
> Je suis en train de travailler sur des map dont j'ai défini la clé suivante.
>
> class MRange
> {
> private:
> char * a;
> size_t s;
> public:
> MRange(void * a, size_t size);
> friend bool operator(const MRange &left, const MRange &right) {
> return (left.a + left.s <= right.a);}
> };
re-définir plus proprement ?
Je fais pas de C++ au quotidient, et comme tu ne fournis pas d'ECM,
je vais pas tester de solution détaillée.
Mais d'après la doc, un souci c'est que ton truc n'est pas un "Strict Weak
Ordering" puisque
MRange x("bla", 0)
donnera
f(x,x) == true
ce qui est interdit.
Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
hey...@gmail.com
Sep 24, 2012, 9:23:05 AM9/24/12
to
Le lundi 24 septembre 2012 13:20:14 UTC+2, Marc Boyer a écrit :
Certes, l'opérateur de comparaison est à manier avec prudence. Dans mon cas, MRange est un intervalle mémoire, dont 'a' est l'adresse, et 's' la taille. 's' ne peut donc pas être égale à zéro.
Ce que j'aimerais savoir c'est comment procède la fonction find() d'un map pour savoir si elle a trouvé le bon élément, et notamment comme fait-elle pour déterminer qu'un élément n'est pas dans le map. Pour cela il me semble qu'il lui faut obligatoirement un opérateur ==. Elle pourrait soit le déduire de l'opérateur < (comportement par défaut) soit utiliser l'opérateur d'égalité s'il était défini.
Dans mon livre (Stroustrup), il est juste indiqué que si un opérateur de comparaison est fourni, il est utilisé (en priorité sur l'opérateur ==, sous entendu natif) pour tester l'égalité. Mais rien n'est dit pour le cas ou l'opérateur == est surchargé...J'imagine qu'il n'est pas utilisé mais j'aurais aimé une confirmation.
AG.
> Le 24-09-2012, heyji2 a écrit :
>
> > Bonjour,
>
> >
>
> > Je suis en train de travailler sur des map dont j'ai défini la clé suivante.
>
> >
>
> > class MRange
>
> > {
>
> > private:
>
> > char * a;
>
> > size_t s;
>
> > public:
>
> > MRange(void * a, size_t size);
>
> > friend bool operator(const MRange &left, const MRange &right) {
>
> > return (left.a + left.s <= right.a);}
>
> > };
>
>
>
> Est-ce que ce ne serait pas plutôt l'opérateur de comparaison qu'il faudrait
>
> re-définir plus proprement ?
>
>
>
> Je fais pas de C++ au quotidient, et comme tu ne fournis pas d'ECM,
>
> je vais pas tester de solution détaillée.
>
>
>
> Mais d'après la doc, un souci c'est que ton truc n'est pas un "Strict Weak
>
> Ordering" puisque
>
> MRange x("bla", 0)
>
> donnera
>
> f(x,x) == true
>
> ce qui est interdit.
Bonjour Marc,
>
> > Bonjour,
>
> >
>
> > Je suis en train de travailler sur des map dont j'ai défini la clé suivante.
>
> >
>
> > class MRange
>
> > {
>
> > private:
>
> > char * a;
>
> > size_t s;
>
> > public:
>
> > MRange(void * a, size_t size);
>
> > friend bool operator(const MRange &left, const MRange &right) {
>
> > return (left.a + left.s <= right.a);}
>
> > };
>
>
>
> Est-ce que ce ne serait pas plutôt l'opérateur de comparaison qu'il faudrait
>
> re-définir plus proprement ?
>
>
>
> Je fais pas de C++ au quotidient, et comme tu ne fournis pas d'ECM,
>
> je vais pas tester de solution détaillée.
>
>
>
> Mais d'après la doc, un souci c'est que ton truc n'est pas un "Strict Weak
>
> Ordering" puisque
>
> MRange x("bla", 0)
>
> donnera
>
> f(x,x) == true
>
> ce qui est interdit.
Certes, l'opérateur de comparaison est à manier avec prudence. Dans mon cas, MRange est un intervalle mémoire, dont 'a' est l'adresse, et 's' la taille. 's' ne peut donc pas être égale à zéro.
Ce que j'aimerais savoir c'est comment procède la fonction find() d'un map pour savoir si elle a trouvé le bon élément, et notamment comme fait-elle pour déterminer qu'un élément n'est pas dans le map. Pour cela il me semble qu'il lui faut obligatoirement un opérateur ==. Elle pourrait soit le déduire de l'opérateur < (comportement par défaut) soit utiliser l'opérateur d'égalité s'il était défini.
Dans mon livre (Stroustrup), il est juste indiqué que si un opérateur de comparaison est fourni, il est utilisé (en priorité sur l'opérateur ==, sous entendu natif) pour tester l'égalité. Mais rien n'est dit pour le cas ou l'opérateur == est surchargé...J'imagine qu'il n'est pas utilisé mais j'aurais aimé une confirmation.
AG.
Jean-Marc Bourguet
Sep 24, 2012, 9:48:43 AM9/24/12
to
hey...@gmail.com writes:
> Ce que j'aimerais savoir c'est comment procède la fonction find() d'un map
> pour savoir si elle a trouvé le bon élément, et notamment comme fait-elle
> pour déterminer qu'un élément n'est pas dans le map. Pour cela il me semble
> qu'il lui faut obligatoirement un opérateur ==. Elle pourrait soit le
> déduire de l'opérateur < (comportement par défaut) soit utiliser
> l'opérateur d'égalité s'il était défini.
La map utilise son troisieme parametre template qui doit etre une
> Ce que j'aimerais savoir c'est comment procède la fonction find() d'un map
> pour savoir si elle a trouvé le bon élément, et notamment comme fait-elle
> pour déterminer qu'un élément n'est pas dans le map. Pour cela il me semble
> qu'il lui faut obligatoirement un opérateur ==. Elle pourrait soit le
> déduire de l'opérateur < (comportement par défaut) soit utiliser
> l'opérateur d'égalité s'il était défini.
relation d'ordre. On ne demande pas de relation d'egalite en plus (qui
devrait de toute facon etre coherente avec la relation d'ordre pour que
la map puisse en faire qqch, alors autant ne pas en accepter).
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
hey...@gmail.com
Sep 24, 2012, 10:16:30 AM9/24/12
to
Le lundi 24 septembre 2012 15:48:44 UTC+2, Jean-Marc Bourguet a écrit :
> La map utilise son troisieme parametre template qui doit etre une
>
> relation d'ordre.
Bonjour Jean-Marc,
> La map utilise son troisieme parametre template qui doit etre une
>
> relation d'ordre.
Dans mon cas, je ne fourni pas le troisième paramètre template à mon map. C'est less<MRange> qui est utilisé par défaut à la place, et qui utilise la surcharge de l'opérateur < sur les MRange (que je fourni). Cela fait-il une différence ?
AG.
Jean-Marc Bourguet
Sep 24, 2012, 10:39:26 AM9/24/12
to
dit, assert(!(a<a)) ) et total (autrement dit, tu dois pouvoir comparer
n'importe quelle paire d'element mis dans la map).
Marc Boyer
Sep 24, 2012, 10:48:58 AM9/24/12
to
> Le lundi 24 septembre 2012 13:20:14 UTC+2, Marc Boyer a écrit :
> Bonjour Marc,
>
> Certes, l'opérateur de comparaison est à manier avec prudence.
> Dans mon cas, MRange est un intervalle mémoire, dont 'a' est
> l'adresse, et 's' la taille. 's' ne peut donc pas être égale à zéro.
C'est parce qu'il y avait un 0 dans ton exemple initial (mais
> Bonjour Marc,
>
> Certes, l'opérateur de comparaison est à manier avec prudence.
> Dans mon cas, MRange est un intervalle mémoire, dont 'a' est
> l'adresse, et 's' la taille. 's' ne peut donc pas être égale à zéro.
c'était l'adresse).
> Ce que j'aimerais savoir c'est comment procède la fonction find()
> d'un map pour savoir si elle a trouvé le bon élément, et notamment
> comme fait-elle pour déterminer qu'un élément n'est pas dans le map.
à l'intérieur plutôt que de lire la spécification.
Je pense que quand on a un bug, c'est bien de revenir à la
spec plutôt que de jouer au devin.
Perso, je ne sais pas comment fonctionne map, mais ton
opérateur de comparaison me semble bizarre. Et comme tu ne
donnes pas d'ECM, et peux d'explication, l'effort pour
t'aider est trop important.
Alain Ketterlin
Sep 24, 2012, 11:23:25 AM9/24/12
to
hey...@gmail.com writes:
[...]
être fourni. Ici, c'est la comparaison (un Strict Weak Ordering). Il n'y
a pas besoin d'égalité, donc op== n'est pas utilisé. (Si tu veux le
vérifier, définis-en un en private.)
Très souvent, map utilise des arbres red-black, qui est une classe
particulière d'arbres binaires de recherche. Dans ces arbres, la
recherche d'une valeur se fait en la comparant à la valeur du noeud en
cours de visite, puis on cherche à gauche si inférieur et à droite si
supérieur. Si aucun des deux n'est vrai, alors les valeurs sont égales.
Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
soient dijoints), ta définition ne répond pas aux critères, en
particulier la transitivité de l'équivalence.
-- Alain.
[...]
> Ce que j'aimerais savoir c'est comment procède la fonction find() d'un
> map pour savoir si elle a trouvé le bon élément, et notamment comme
> fait-elle pour déterminer qu'un élément n'est pas dans le map. Pour
> cela il me semble qu'il lui faut obligatoirement un opérateur ==. Elle
> pourrait soit le déduire de l'opérateur < (comportement par défaut)
> soit utiliser l'opérateur d'égalité s'il était défini.
Voir le message de Jean-Marc : c'est la doc qui t'indiquera ce qui doit
> map pour savoir si elle a trouvé le bon élément, et notamment comme
> fait-elle pour déterminer qu'un élément n'est pas dans le map. Pour
> cela il me semble qu'il lui faut obligatoirement un opérateur ==. Elle
> pourrait soit le déduire de l'opérateur < (comportement par défaut)
> soit utiliser l'opérateur d'égalité s'il était défini.
être fourni. Ici, c'est la comparaison (un Strict Weak Ordering). Il n'y
a pas besoin d'égalité, donc op== n'est pas utilisé. (Si tu veux le
vérifier, définis-en un en private.)
Très souvent, map utilise des arbres red-black, qui est une classe
particulière d'arbres binaires de recherche. Dans ces arbres, la
recherche d'une valeur se fait en la comparant à la valeur du noeud en
cours de visite, puis on cherche à gauche si inférieur et à droite si
supérieur. Si aucun des deux n'est vrai, alors les valeurs sont égales.
Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
soient dijoints), ta définition ne répond pas aux critères, en
particulier la transitivité de l'équivalence.
-- Alain.
Heyji
Sep 25, 2012, 4:07:13 AM9/25/12
to
Le lundi 24 septembre 2012 17:23:26 UTC+2, Alain Ketterlin a écrit :
> Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
>
> soient dijoints), ta définition ne répond pas aux critères, en
>
> particulier la transitivité de l'équivalence.
Merci Alain, c'est effectivement par la que ça blesse...C'est en fait déjà un problème de définir une relation sur l'ensemble des Intervalles "à condition qu'ils soient disjoints" car tu peux facilement avoir trois intervalles a, b, c reliés tels que a R b et b R c (a et b disjoints, et b et c disjoints) mais a et c non disjoints.
> Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
>
> soient dijoints), ta définition ne répond pas aux critères, en
>
> particulier la transitivité de l'équivalence.
Je vais continuer d'investiguer pour voir s'il n'y a pas moyen de bidouiller un truc propre, mais j'ai peu d'espoir. Les intervalles de boost n'ont pas l'air d'en parler par exemple.
AG.
PS: voici l'ECM pour ceux que ça amuse.
#include <iostream>
#include <map>
class MRange
{
public:
MRange(void * addr, size_t size) { a = (char *)addr; s = size;}
friend bool operator<(const MRange &left, const MRange &right) {
return (left.a + left.s <= right.a);}
private:
char * a;
size_t s;
};
char * a;
size_t s;
int main(void)
{
std::map<MRange,int> memory;
MRange a1((void *)0,10);
MRange a2((void *)5,10);
MRange a3((void *)12,10);
memory[a1]=0;
memory[a3]=1;
std::map<MRange,int>::iterator i = memory.find(a2);
if(i!=memory.end())
std::cout << i->second << "\n";
else
std::cout << "not found\n";
std::cout << memory.count(a2) << "\n";
}
Alain Ketterlin
Sep 25, 2012, 5:17:08 AM9/25/12
to
Heyji <hey...@gmail.com> writes:
> Le lundi 24 septembre 2012 17:23:26 UTC+2, Alain Ketterlin a écrit :
>
>> Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
>> soient dijoints), ta définition ne répond pas aux critères, en
>> particulier la transitivité de l'équivalence.
>
> Merci Alain, c'est effectivement par la que ça blesse...C'est en fait
> déjà un problème de définir une relation sur l'ensemble des
> Intervalles "à condition qu'ils soient disjoints" car tu peux
> facilement avoir trois intervalles a, b, c reliés tels que a R b et b
> R c (a et b disjoints, et b et c disjoints) mais a et c non disjoints.
Donc tu ne peux pas utiliser map ou set ou les arbres binaires de
> Le lundi 24 septembre 2012 17:23:26 UTC+2, Alain Ketterlin a écrit :
>
>> Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
>> soient dijoints), ta définition ne répond pas aux critères, en
>> particulier la transitivité de l'équivalence.
>
> Merci Alain, c'est effectivement par la que ça blesse...C'est en fait
> déjà un problème de définir une relation sur l'ensemble des
> Intervalles "à condition qu'ils soient disjoints" car tu peux
> facilement avoir trois intervalles a, b, c reliés tels que a R b et b
> R c (a et b disjoints, et b et c disjoints) mais a et c non disjoints.
recherche en général, qui imposent tous un "Strict Weak Ordering", ce
que tu n'as pas.
Ce que tu cherches s'appelle un interval-tree, il me semble cf.
http://en.wikipedia.org/wiki/Interval_tree
> Je vais continuer d'investiguer pour voir s'il n'y a pas moyen de
> bidouiller un truc propre, mais j'ai peu d'espoir. Les intervalles de
> boost n'ont pas l'air d'en parler par exemple.
http://stackoverflow.com/questions/5407814/c-interval-tree-implementation
Il semble que Boost l'ait fait.
-- Alain.
Marc Boyer
Sep 25, 2012, 6:31:22 AM9/25/12
to
Le 25-09-2012, Heyji <hey...@gmail.com> a écrit :
> Le lundi 24 septembre 2012 17:23:26 UTC+2, Alain Ketterlin a écrit :
>
>> Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
>> soient dijoints), ta définition ne répond pas aux critères, en
>> particulier la transitivité de l'équivalence.
>
> Merci Alain, c'est effectivement par la que ça blesse...C'est en fait déjà un
> problème de définir une relation sur l'ensemble des Intervalles
> "à condition qu'ils soient disjoints" car tu peux facilement avoir
> trois intervalles a, b, c reliés tels que a R b et b R c (a et b disjoints,
> et b et c disjoints) mais a et c non disjoints.
Je ne comprends pas bien le problème. Si le seul objectif de ton opérateur
> Le lundi 24 septembre 2012 17:23:26 UTC+2, Alain Ketterlin a écrit :
>
>> Si je me souviens bien (un ordre sur des intervalles à condition qu'ils
>> soient dijoints), ta définition ne répond pas aux critères, en
>> particulier la transitivité de l'équivalence.
>
> Merci Alain, c'est effectivement par la que ça blesse...C'est en fait déjà un
> problème de définir une relation sur l'ensemble des Intervalles
> "à condition qu'ils soient disjoints" car tu peux facilement avoir
> trois intervalles a, b, c reliés tels que a R b et b R c (a et b disjoints,
> et b et c disjoints) mais a et c non disjoints.
de comparaison, c'est de ranger dans une map, un bête ordre lexicographique
devrait suffire, non ?
if (left.a == right.a)
return left.s < right.s;
else
return left.a < right.a;
Sinon, quelle est l'autre objectif que tu n'as pas donné ?
hey...@gmail.com
Sep 25, 2012, 8:05:17 AM9/25/12
to
Le mardi 25 septembre 2012 13:01:02 UTC+2, Marc Boyer a écrit :
> Sinon, quelle est l'autre objectif que tu n'as pas donné ?
Bon allez, je déballe parce que ça intéresse:
> Sinon, quelle est l'autre objectif que tu n'as pas donné ?
Je veux juste ranger dans un container des intervalles disjoints. Mais je veux aussi pouvoir, lors de l'insertion d'un intervalle quelconque, vérifier s'il recouvre un ou plusieurs intervalles déjà insérés auquel cas il me faut retirer ces intervalles, calculer les intersections, construire autant d'intervalles disjoints, puis réinsérer ces nouveaux intervalles.
Je ne connaissais pas les "arbres d'intervalle" d'Alain, peut être est-ce un cas particulier de ces conteneurs. Il faut que je regarde de plus près car ça pourrait m'éviter beaucoup de code.
@Alain: j'avais lu la doc sur les intervalles de Boost, et je n'y ai vu nul part la mention "strict weak ordering". De fait, ça n'est pas possible car il faut que les intervalles soient disjoints. ils fournissent un comparateur approchant, qui jette une exception lorsque la comparaison est indécidable, mais ça n'est pas utilisable dans un map pour autant.
Heyji
Sep 25, 2012, 8:15:52 AM9/25/12
to
Le mardi 25 septembre 2012 11:17:09 UTC+2, Alain Ketterlin a écrit :
> http://stackoverflow.com/questions/5407814/c-interval-tree-implementation
> Il semble que Boost l'ait fait.
> -- Alain.
Oui Alain, je crois que c'est exactement ce dont j'ai besoin: interval_map.
> http://stackoverflow.com/questions/5407814/c-interval-tree-implementation
> Il semble que Boost l'ait fait.
> -- Alain.
Merci beaucoup !
Alain Ketterlin
Sep 25, 2012, 1:02:01 PM9/25/12
to
hey...@gmail.com writes:
> Le mardi 25 septembre 2012 13:01:02 UTC+2, Marc Boyer a écrit :
>
>> Sinon, quelle est l'autre objectif que tu n'as pas donné ?
> Le mardi 25 septembre 2012 13:01:02 UTC+2, Marc Boyer a écrit :
>
>> Sinon, quelle est l'autre objectif que tu n'as pas donné ?
> Je veux juste ranger dans un container des intervalles disjoints. Mais
> je veux aussi pouvoir, lors de l'insertion d'un intervalle quelconque,
> vérifier s'il recouvre un ou plusieurs intervalles déjà insérés auquel
> cas il me faut retirer ces intervalles, calculer les intersections,
> construire autant d'intervalles disjoints, puis réinsérer ces nouveaux
> intervalles.
Pour le coup, c'est moi qui n'avais pas totalement compris.
> je veux aussi pouvoir, lors de l'insertion d'un intervalle quelconque,
> vérifier s'il recouvre un ou plusieurs intervalles déjà insérés auquel
> cas il me faut retirer ces intervalles, calculer les intersections,
> construire autant d'intervalles disjoints, puis réinsérer ces nouveaux
> intervalles.
Tu peux utiliser des arbres d'intervalle, mais c'est un peu dommage si
les intervalles sont vraiment disjoints : dans ce cas, la borne inf (ou
sup) suffit pour garder l'ordre, et tu peux utiliser (a.right <
b.left || b.right < a.left ) pour la comparaison.
Par contre, tu as une opération (qui n'est pas find) qui consiste à
chercher tous les intervalles qui intersectent le nouveau[a,b]. Il doit
y avoir un moyen de faire ça avec lower_bound([-infini,b]) et
upper_bound([a,+infini]). Ensuite il faut traverser ce "range" et
tester. Je dis ça sans avoir vraiment réfléchi.
> Je ne connaissais pas les "arbres d'intervalle" d'Alain, peut être
> est-ce un cas particulier de ces conteneurs. Il faut que je regarde de
> plus près car ça pourrait m'éviter beaucoup de code.
> @Alain: j'avais lu la doc sur les intervalles de Boost, et je n'y ai
> vu nul part la mention "strict weak ordering". De fait, ça n'est pas
> possible car il faut que les intervalles soient disjoints. ils
> fournissent un comparateur approchant, qui jette une exception lorsque
> la comparaison est indécidable, mais ça n'est pas utilisable dans un
> map pour autant.
que tout le monde y fasse référence.
-- Alain.
0 new messages