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++ clé ad-hoc pour un map

clé ad-hoc pour un map

13 réponses
Avatar
heyji2
Bonjour,=20

Je suis en train de travailler sur des map dont j'ai d=E9fini la cl=E9 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 <=3D right.a);}
};


=E7a m'a tout l'air de fonctionner comme attendu, notamment deux MRange "di=
ff=E9rent" du type MRange(0x0,10) et MRange(0x1,5) sont en fait consid=E9r=
=E9s comme =E9gaux (m=EAme cl=E9) dans le map suivant:=20

std::map<MRange,int> memory;

Ceci provient du fait que (et c'est l=E0 que je ne ma=EEtrise pas trop) l'o=
p=E9rateur =3D=3D est d=E9duit de la d=E9finition de l'op=E9rateur < (au mo=
ins dans le fonctionnement du map).=20

Ma question est donc la suivante: Que se passe-t-il si je red=E9finit l'op=
=E9rateur =3D=3D comme ci-dessous ? Cela risque-t-il de changer l'ordre de =
mon map ? Et si non, est-ce garanti ?

friend bool operator=3D=3D(const MRange & left, const MRange &right)
{
return ((left.a=3D=3Dright.a) && (left.s =3D=3D right.s))
}

Merci pour vos lumi=E8res.=20

AG.


=20
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
Avatar
Marc Boyer
Le 24-09-2012, 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.


Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
Avatar
heyji2
Le lundi 24 septembre 2012 13:20:14 UTC+2, Marc Boyer a écrit :
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'i l 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 "Stric t Weak

Ordering" puisque

MRange x("bla", 0)

donnera

f(x,x) == true

ce qui est interdit.


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.
Avatar
Jean-Marc Bourguet
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 so it le
déduire de l'opérateur < (comportement par défaut) soit ut iliser
l'opérateur d'égalité s'il était défini.



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
Avatar
heyji2
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,

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.
Avatar
Jean-Marc Bourguet
writes:

Le lundi 24 septembre 2012 15:48:44 UTC+2, Jean-Marc Bourguet a écri t :

La map utilise son troisieme parametre template qui doit etre une

relation d'ordre.


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 MRa nge (que je fourni). Cela fait-il une différence ?



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
Avatar
Marc Boyer
Le 24-09-2012, a écrit :
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
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.



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
Avatar
Alain Ketterlin
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 notamm ent 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
ê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.
Avatar
Heyji
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 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";
}
Avatar
Alain Ketterlin
Heyji 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ère s, 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'ensemb le 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
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.



De parler de quoi exactement ?

http://stackoverflow.com/questions/5407814/c-interval-tree-implementation

Il semble que Boost l'ait fait.

-- Alain.
Avatar
Marc Boyer
Le 25-09-2012, Heyji 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
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
1 2