Comparateur "custom" de std::map
Bonjour à tous, à toutes, la forme ? ;)
Alors voilà, j'ai un petit problème.. Je bosse en ce moment sur les graphes et sur les recherches de meilleur chemin. De tels algorithmes imposent très souvent de tenir une liste rangée ( en l'occurrence, une map ) de points, de telle sorte que le premier point de la dite liste soit celui qui satisfait le plus possible telle ou telle exigence.
Dans mon exemple, j'utilise une map de <points,char>, et je voudrais que le premier élément de la liste soit celui dont la clé ( le point ) est le plus proche du point d'arrivée.
En fait j'y suis déjà arrivé, le problème vient quand deux points sont équidistants ( me sortez pas vos histoire d'équidistant avec le dragon, je vois déjà venir les fans de kaamelott :) ) équidistants, disais-je, du point d'arrivée. En fait, lorsqu'un nouveau point est ajouté à la liste et qu'il est aussi loin du point d'arrivée que ne l'est déjà un autre point de la liste, le nouveau point remplace le précédent, dans sa position dans la map ( ce qui ne me dérange pas ) et dans sa clé/valeur ( ce qui me dérange beaucoup plus ! ). Voyez plutôt :
Code:
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
34
35
36
37
38
| #include <SFML/Graphics.hpp>
#include <map>
#include <iostream>
#include <cmath>
/* Que ceci n'effraie pas certains : un sf::Vector2i est exactement la même chose qu'un std::pair<int,int>, à ceci près que ses deux "pairs" sont accessibles par des .x et .y, au lieu de .first et .second */
typedef sf::Vector2i Point;
Point start(5,6), goal(16,6);
// Le comparateur de map..
class comp
{
public:
bool operator()(const Point X,const Point Y)
{
// si X est sctrictement plus proche de goal que ne l'est Y, on renvoie TRUE. Sinon, on renvoie FALSE.
return sqrtf((goal.x-X.x)*(goal.x-X.x)+(goal.y-X.y)*(goal.y-X.y)) < sqrtf((goal.x-Y.x)*(goal.x-Y.x)+(goal.y-Y.y)*(goal.y-Y.y));
}
};
int main()
{
std::map<Point,char,comp> map;
Point a(5,7), b(10,3), c(15,5), d(17,5);
map[d]='d';
map[a]='a';
map[c]='c';
map[b]='b';
map.erase(map.begin()->first);
std::cout<<"point le plus proche : "<<map.begin()->second;
return 0;
} |
Ici, c est aussi loin de goal que d. Problème : lorsque j'ajoute c à la map, après d donc, il remplace d par c. Conséquence : lorsque je supprime c, le premier élément n'est plus d mais b. Comment faire pour que tel ne soit pas le cas ? J'ai bien essayé de remplacer < par <= dans le comparateur mais il semblerait que ne soit pas la bonne solution..
Des idées ? :)
Mr Pchoun !
