clé ad-hoc pour un map
Le
heyji2
Bonjour,
Je suis en train de travailler sur des map dont j'ai défini la clé suiv=
ante.
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 "di=
ffé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'o=
pérateur == est déduit de la définition de l'opérateur < (au mo=
ins 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é suiv=
ante.
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 "di=
ffé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'o=
pérateur == est déduit de la définition de l'opérateur < (au mo=
ins 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.
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.
Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
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.
Ce que j'aimerais savoir c'est comment procède la fonction find() d'un ma p pour savoir si elle a trouvé le bon élément, et notamment comme fai t-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 po urrait soit le déduire de l'opérateur < (comportement par défaut) soi t utiliser l'opérateur d'égalité s'il était défini.
Dans mon livre (Stroustrup), il est juste indiqué que si un opérateur d e 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'es t pas utilisé mais j'aurais aimé une confirmation.
AG.
La map utilise son troisieme parametre template qui doit etre une
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
Bonjour Jean-Marc,
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). Ce la fait-il une différence ?
AG.
Non. Mais il faut que ce soit une relation d'ordre strict (autrement
dit, assert(!(a<a)) ) et total (autrement dit, tu dois pouvoir comparer
n'importe quelle paire d'element mis dans la map).
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
C'est parce qu'il y avait un 0 dans ton exemple initial (mais
c'était l'adresse).
J'ai eu le même travers: vouloir savoir comment c'est fait
à 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.
Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
[...]
Voir le message de Jean-Marc : c'est la doc qui t'indiquera ce qui doit
ê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.
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 Interval les "à condition qu'ils soient disjoints" car tu peux facilement avoir tr ois 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 vais continuer d'investiguer pour voir s'il n'y a pas moyen de bidouille r un truc propre, mais j'ai peu d'espoir. Les intervalles de boost n'ont pa s 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;
};
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 foundn";
std::cout << memory.count(a2) << "n";
}
Donc tu ne peux pas utiliser map ou set ou les arbres binaires de
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
De parler de quoi exactement ?
http://stackoverflow.com/questions/5407814/c-interval-tree-implementation
Il semble que Boost l'ait fait.
-- Alain.
Je ne comprends pas bien le problème. Si le seul objectif de ton opérateur
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é ?
Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet