Discussion :

[casafa]

Bonjour,

Si je crée une map de cette façon : std::map<float, int>, comment la comparaison entre les clefs va elle se faire ?

Un simple == entre deux float ?

Merci d'avance...

[Laurent Gomila]

std::map n'utilise pas l'égalité, mais une relation d'ordre. Cela utilisera toujours et uniquement l'opérateur <.

[casafa]

Merci pour ta réponse.

Quand on utilise la fonction insert de std::map, je comprend parfaitement qu'il n'a pas besoin d'utiliser "==".

Mais quand on va rechercher un élément comme ceci: maMap[2.5], il doit bien utiliser le "==" ? autrement je voit pas comment il ferait !

[Ksempac]

C'est du a une propriété mathematique toute bete, mais a laquelle on ne pense pas immédiatement : si 2 nombres sont égaux, A < B et B < A renvoient tous les deux FALSE.

Exemple :

A = 2, B = 3.
A < B renvoie TRUE
B < A renvoie FALSE

A = 3, B = 2
A < B renvoie FALSE
B < A renvoie TRUE

A = 2, B = 2
A < B renvoie FALSE
B < A renvoie FALSE

C'est une chose qu'il ne faut pas oublier de prendre en compte lorsqu'on surcharge l'opérateur <

A part ca, meme pour un insert on a besoin de reconnaitre les cas d'egalité, puisque la map doit s'assurer de ne pas avoir de doublon

[casafa]

Ouais je vois mais donc un map<float, int> ça n'a fonctionnera pas bien dans ce cas à cause de l'imprecision des float alors :

float a=1.0f;
float b=2.1f-1.1f;
maMap[a] = 5;
maMap[b] = 8;

Il risque de m'ajouter 2 données différentes dans la map alors que "a" et "b" sont cencé être de la même valeur. C'est bien ça ?

[zais_ethael]

L'imprécision dans les calculs sur flottant n'apparait pas au petit bonheur la chance, dans ton calcul a et b contiennent exactement la même chose.
Cela n'a de risque d'arriver que si tu fais des division. Par exemple il se peut que dans les formules 2.0/3.0 et (1.0/3.0)*2.0 les tout derniers bits utilisés pour représenter la valeur 0.666... soient différents.
Dans l'absolu, il est vrai que si il y a une différence de ne serais-ce qu'un millionième entre deux flottants map créera deux entrées différentes.
Si cela te pose un problème, il est possible de personnaliser le foncteur utilisé par map pour faire les comparaisons pour lui imposer une précision limitée (à 1,2,3 chiffres après la virgule par exemple).

[NiamorH]

Peut être y a-t-il un problème de conception derrière ?

De toute manière, si tu dois faire quelque chose de vraiment précis, cela sera vrai sur toute ton appli et il va falloir utiliser une autre représentation pour les flottants.

Si tu peux te permettre des imprecisions dans les calculs ailleurs dans l'appli, alors tu peux ici aussi et il te faudra considérer égales des valeurs à x.xx près.

Tu dois pouvoir changer le prédicat qui fait la comparaison dans la map, comme j'ai eu à le faire récement pour un std::set.

[koala01]

Salut,

C'est une chose qu'il ne faut pas oublier de prendre en compte lorsqu'on surcharge l'opérateur <

A part ca, meme pour un insert on a besoin de reconnaitre les cas d'egalité, puisque la map doit s'assurer de ne pas avoir de doublon

Etant donné que la std::map utilise seulement l'opérateur plus petit, elle considère que si
a n'est pas plus petit que b et que
b n'est pas plus petit que a alors
a est égal à b...

Il faut noter que, dans certains cas, cela risque d'apporter quelques bugs originaux (même si je n'ai aucune idée de ce qu'ils peuvent être )

Comme quoi, il y a parfaitement moyen de ne travailler qu'avec l'opérateur "plus petit"

Evidemment, il reste le fait que les réels (floats ou doubles d'ailleurs) souffrent d'une imprécision qui est, principalement due à la représentation binaire.

Comme toute comparaison entre des réels, il faut donc penser à prendre en compte le "décalage" en dessous duquel un nombre reste identique, c'est à dire s'il se trouve entre les X - std::limits<float>::epsilon() et X + std::limits<float>::epsilon() (où X est le nombre utilisé )

L'un dans l'autre, ca pourrait très bien servir de "théorie" pour créer le foncteur ad-hoc

[casafa]

Merci pour vos réponses.

zais_ethael j'aurais logiquement le même raisonnement que toi à propos des float mais :

1) Dans la FAQ, j'ai vu :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
float f1 = 0.1f;
float f2 = 1.1f;
float f3 = f2 - f1;
 
// Version incorrecte ne tenant pas compte des imprécisions
if (f3 == 1.0f)
{
    // Pratiquement jamais vrai !
}

http://cpp.developpez.com/faq/cpp/?p...ions_flottants

2) Ce programme m'affiche "2" à l'execution :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <map>
using namespace std;
 
int main()
{
	std::map<float, int> maMap;
 
	float a=1.0f;
	float b=2.1f-1.1f;
	maMap[a] = 5;
	maMap[b] = 8;
 
	cout<<maMap.size()<<endl;
 
	return 0;
}

Alors que si je remplace la ligne "float b=2.1f-1.1f;" par "float b=1.0f;",le programme m'affiche "1" !!!

[NiamorH]

Tu n'as pas répondu si travailler avec des imprecisions pour la map serait une option ?

Si oui, dans l'esprit, la solution serait ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <map>
using namespace std;
 
 
struct PredicatLessFloat
{
  static float const imprecision;
 
  bool operator () ( float const & f1, float const & f2 ) const
  {
    float f3 = f2 - f1 - imprecision;
    return f3 > 0;
  }
};
 
float const PredicatLessFloat::imprecision = 0.000001;
 
 
int main()
{
  std::map<float, int, PredicatLessFloat> maMap;
 
  float a=1.0f;
  float b=2.1f-1.1f;
  maMap[a] = 5;
  maMap[b] = 8;
 
  // affiche 1
  cout<<maMap.size()<<endl;
 
  return 0;
}

[JolyLoic]

Un tel prédicat ne correspond pas à ce qui est requis pour une map. Il faut en effet que ce soit un "strict weak ordering", c'est à dire (avec a==b défini comme !(a<b) && !(b<a)):

- !(a<a)
- a<b && b<c => a<c
- a==b && b==c => b==c

Or avec ta proposition de prédicat, le troisière point n'est pas respecté. Imaginons une précision de 0.1 et les valeurs a=0.91, b=1, c=1.09.

On a bien a==b (car, à cette précision, a n'est ni plus grand ni plus petit que b).
On a bien b==c (car, à cette précision, b n'est ni plus grand ni plus petit que c).

Par contre, on a a<c.


Conclusion : Indexer une map par des flottants n'est probablement pas une bonne idée. Il faudrait voir quel est le problème initial pour faire une contre proposition.

[Jean-Marc.Bourguet]

L'imprécision dans les calculs sur flottant n'apparait pas au petit bonheur la chance,

C'est vrai et c'est important.

Mais

dans ton calcul a et b contiennent exactement la même chose.

est faux.

Cela n'a de risque d'arriver que si tu fais des division.

est faux.

Ca arrive chaque fois que le resultat d'un calcul n'est pas exactement representable. Ca peut arriver avec des additions et des soustractions, et ca arrive souvent quand on convertit d'une representation a une autre -- en particulier de la representation decimale utilisee pour les litteraux a la representation binaire interne.

[zais_ethael]

Ha, je viens d'aller voir quelques sites et il semblerait que mon prof d'assembleur n'avait pas jugé utile de nous dire que les réels en base 10 n'étaient pas forcément représentables en base 2. Autant pour moi.

[droggo]

Qoe,

Ha, je viens d'aller voir quelques sites et il semblerait que mon prof d'assembleur n'avait pas jugé utile de nous dire que les réels en base 10 n'étaient pas forcément représentables en base 2. Autant pour moi.

Une petite réflexion te l'aurait appris, sinon il faudrait une résolution infinie.