Virgule flottante clés dans std:carte
Le code suivant est censé trouver la clé 3.0
dans un std::map
qui existe. Mais en raison de la précision en virgule flottante, il ne sera pas trouvé.
map<double, double> mymap;
mymap[3.0] = 1.0;
double t = 0.0;
for(int i = 0; i < 31; i++)
{
t += 0.1;
bool contains = (mymap.count(t) > 0);
}
Dans l'exemple ci-dessus, contains
sera toujours false
.
Ma solution actuelle est il suffit de multiplier t
de 0,1 au lieu de l'ajout de 0,1, comme ceci:
for(int i = 0; i < 31; i++)
{
t = 0.1 * i;
bool contains = (mymap.count(t) > 0);
}
Maintenant, la question:
Est-il un moyen d'introduire un fuzzyCompare à la std::map
si j'utilise double
clés?
La solution commune pour nombre à virgule flottante comparaison est généralement quelque chose comme a-b < epsilon
. Mais je ne vois pas de moyen simple de le faire avec std::map
.
Dois-je vraiment d'encapsuler le double
type dans une classe et écraser operator<(...)
pour mettre en œuvre cette fonctionnalité?
- Comment fermer est assez proche? Il semble que vous pourriez réellement envie de les stocker et de rechercher via arrondie clés.
- Dans une sorte de revers pour votre solution de contournement, et si les chars sont tous d'un niveau spécifié de chiffres de précision, vous pouvez stocker les clés que les entiers, les valeurs à virgule flottante être multiplié par certains facteur d'échelle et stockés comme ça.
- J'ai pensé à ça, mais je vais avoir des problèmes en fonction de la résolution je risque de débordement facilement.
- Vous devez être conscient que même votre solution de contournement peut échouer - vous eu de la chance sur l'arrondissement pour la multiplier.
0.1
ne peut pas être représenté précisément en base 2. - oui, je sais. C'est pourquoi je voulais une vraie solution. Mais vous devez admettre, c'est un bel exemple pour montrer comment float comparaisons peuvent conduire à un comportement indéterminé. 🙂
- Voir stackoverflow.com/questions/4816156/...
- Votre code fonctionne correctement. Lorsque vous ajoutez le
double
0.1
à lui-même dix fois, vous n'obtenez pas1.0
. - Dans votre cas, vous devriez sans doute utilisés "point fixe" les clés. double peuvent utilement être utilisé comme une clé dans une carte lorsque vous envisagez de l'utiliser pour l'interpolation ou de faire un histogramme. Pour l'un de ces, vous allez utiliser lower_bound à définir la gamme d'une valeur de chutes et à quelle distance entre les limites, il tombe.
Vous devez vous connecter pour publier un commentaire.
Vous pourriez mettre en œuvre propre fonction de comparaison.
Mise à jour: voir Article 40 dans l'efficacité de la STL!
Mis à jour en fonction des suggestions.
comp(a, b) && comp(b, c)
impliquecomp(a, c)
,comp(a, a) == false
, etcomp(a, b)
implique!comp(b, a)
. Cela peut être facile à nettoyer jusqu'à... par exempleown_double_less(-1, -1) == true
siepsilon > 0
std::map
peut facilement conduire à lastd::map
exécution d'un comportement indéfini (y compris, dans la pratique, de s'écraser, en boucle à l'infini, ou de sauter la pile). @jcoffland donne un exemple clair de la façon dont cela peut se produire. Les deux cette réponse, et @MarkRansom réponse, sont téméraire choses à faire pour unstd::map
.Il y a donc quelques problèmes avec l'utilisation de doubles de clés dans un
std::map
.D'abord,
NaN
, ce qui se compare à moins de lui-même est un problème. Si il y a toute chance deNaN
être inséré, utilisez ceci:mais c'est peut-être trop paranoïaque. Ne pas, je le répète, ne pas inclure un epsilon seuil de votre opérateur de comparaison que vous passez à un
std::set
ou similaires: ce sera violer les exigences au niveau des commandes du conteneur, et le résultat imprévisible comportement indéfini.(J'ai placé
NaN
comme supérieure à toutes lesdouble
s, y compris+inf
, dans ma commande, pour aucune bonne raison. Moins de tous lesdouble
s fonctionne également).Donc soit utiliser la valeur par défaut
operator<
, ou le dessus de l'safe_double_less
, ou quelque chose de similaire.Prochaine, je vous conseille l'aide d'un
std::multimap
oustd::multiset
, parce que vous devez recevoir plusieurs valeurs pour chaque recherche. Vous pourriez aussi bien faire de la gestion de contenu une chose tous les jours, au lieu d'un coin de cas, d'augmenter la couverture de test de votre code. (J'ai rarement recommander ces conteneurs), Plus cela bloqueoperator[]
, ce qui n'est pas conseillé de l'utiliser lorsque vous êtes à l'aide de virgule flottante clés.Le point où vous souhaitez utiliser un epsilon est lors d'une requête sur le conteneur. Au lieu d'utiliser directement l'interface, créer une fonction d'assistance comme ceci:
qui fonctionne sur les deux
std::map
etstd::set
(etmulti
versions).(Dans une version plus moderne de la base de code, je m'attends à une
range<?>
objet qui est une meilleure chose pour le retour d'uneequal_range
fonction. Mais pour l'instant, je vais le rendre compatible avecequal_range
).Ce trouve une série de choses dont les touches sont "suffisamment proche" de celui que vous demandez, alors que le récipient maintient ses garanties d'organisation interne et de ne pas exécuter un comportement indéfini.
Pour tester l'existence d'une touche, faites ceci:
et si vous voulez supprimer/remplacer les entrées, vous devez faire face à la possibilité qu'il pourrait y avoir plus d'une entrée frappé.
La plus courte réponse est "ne pas utiliser les valeurs à virgule flottante que les clés pour
std::set
etstd::map
", parce que c'est un peu compliqué.Si vous ne l'utilisez à virgule flottante clés pour
std::set
oustd::map
, presque certainement jamais faire un.find
ou un[]
sur eux, car c'est très très susceptibles d'être une source de bugs. Vous pouvez l'utiliser pour un classement automatique de collecte de choses, tant que l'ordre n'a pas d'importance (c'est à dire, que l'un particulier 1.0 est en avance ou en retard ou exactement au même endroit que l'autre 1.0). Même alors, j'irais avec un multimap/multiset, comme en s'appuyant sur les collisions ou d'absence de celle-ci n'est pas quelque chose que j'avais fier.Raisonnement sur la valeur exacte de l'IEEE valeurs à virgule flottante est difficile, et la fragilité de code en s'appuyant sur ce qui est commun.
const Container& container
. non seulement le déplacement inutile, ça ne fonctionne pas non plus car après l'appel de my_equal_range/key_exists, les déplacés conteneur est vide après l'appel.my_equal_range
voudrez peut-être un non-const
Container
afin de retourner à la non-const_iterator
s. En utilisant la technique ci-dessus, il fonctionne pour les deux.key_exists
pourrait utiliserContainer const&
certes. Enfin, n'oubliez pas quemove
ne bouge pas, et ne&&
références -- de déménagement nécessite de construire un autre objet.return range.first != range.second;
voir, par exemple, certains cas de test ici: ideone.com/oc0PhH . (J'ai essayé de modifier la réponse mais la modification requise à moins de 6 char changement qui semble idiot pour le code).s/=/!/
.find
et[]
et les autres sont susceptibles d'être des sources de bugs. Ajout d'un paragraphe ou trois sur le sujet.Voici un exemple simplifié de l'utilisation de soft-comparer (aka epsilon ou presque égales) peut conduire à des problèmes.
Laisser
epsilon = 2
pour des raisons de simplicité. Mettre1
et4
dans votremap
. Désormais, elle pourrait ressembler à ceci:Donc
1
est la racine de l'arbre.Maintenant placer les numéros de
2
,3
,4
dans cet ordre. Chacun va remplacer la racine, parce qu'il compare égale à elle. Alors vous avezqui est déjà cassé. (N'assumons aucune tentative de rééquilibrer l'arbre est faite.) Nous pouvons aller de l'avant avec
5
,6
,7
:et c'est encore plus brisé, parce que maintenant, si nous nous demandons si
4
est là, il va dire "non", et si nous lui demandons un itérateur pour les valeurs inférieures à7
, il ne comprend pas4
.Même si je dois dire que j'ai utilisé
map
sur la base de cette mauvaise floue comparer opérateur de nombreuses fois dans le passé, et chaque fois que je fouilla un bug, il n'a jamais été pour cette raison. C'est parce que les jeux de données dans mes domaines d'application n'a jamais véritablement quantité de stress-test de ce problème.set
oumap
dans quelque chose comme la Fortune de l'algorithme utilisé pour les diagrammes de Voronoï. Là, vous êtes à la que à la recherche à un emplacement dans l'arbre, si les deux clés sont sur le point de devenir l'égalité.long long
coordonnées sur cette grille. S'assurer que le domaine du problème est à l'intérieur, mais aussi de l'ordre de la gamme delong long
, pour de meilleurs résultats.epsilon
distance (soit Manhattan ou Euclidienne) de votre cible lors de la recherche si quelque chose est à un endroit.map
, comme dansmap<pair<long long, long long>, object>
. Pour l'idée de travail, l'élément doit être placé dans chacune des cellules qui chevauche un cercle de rayon epsilon (ou un carré, pour une distance Manhattan) autour de son emplacement réel. Il est donc logique d'avoir une grille de hauteur environ, ou moins, un epsilon.Comme Naszta dit, vous pouvez mettre en place votre propre fonction de comparaison. Ce qu'il laisse est la clé pour faire ce travail, vous devez vous assurer que la fonction toujours retourne
false
de toutes les valeurs qui sont à l'intérieur de votre tolérance pour l'équivalence.Edit: comme l'a souligné dans de nombreux commentaires de cette réponse et les autres, il y a une possibilité pour que ce mal tourner si les valeurs que vous le nourrissiez sont arbitrairement distribués, parce que vous ne pouvez pas garantir que
!(a<b)
et!(b<c)
résultats dans!(a<c)
. Cette ne serait pas un problème dans la question posée, parce que les chiffres en question sont regroupés autour de incréments de 0,1; aussi longtemps que votre epsilon est assez grand pour tenir compte de tous possible les erreurs d'arrondi, mais est inférieur à 0,05, il sera fiable. Il est extrêmement important que les clés de la carte ne sont jamais moins de 2*epsilon à part.a
,b=a+3ε/4
,c=a+3ε/2
. Nous avons(a<b) == false
,(b<c)==false
, mais(a<c)==true
. Le fait de violer faible stricte de la commande?À l'aide de doubles de clés n'est pas utile. Dès que vous faites de toute l'arithmétique sur les touches, vous n'êtes pas sûr de ce que exactement les valeurs qu'ils ont et ne peuvent donc pas les utiliser pour l'indexation de la carte. La seule raisonnable d'utilisation serait que les touches sont constants.