En plus, si tu part sur le principe d'une classe qui va se charger de gérer les différentes arrêtes sur base de ce que je te propose, cela peut très bien tourner sur quelque chose de relativement simple... meme si on en vient à oublier le heapsort :p
Je m'explique:
Tu part sur une classe (ou une structure) Point "classique", avec un foncteur permettant de déterminer si un point est plus petit qu'un autre (le fameux predicat "less" 
)
Tu crée, pour la facilité, un alias
typedef std::pair<Point,Point> Arrete;
qui te permet de représenter une arrête avec son point "de départ" et son point "d'arrivée".
la création d'une arrête sous cette forme se fait sous la forme de
Arrete obj=std::make_pair(point1, point2);
Tu crées ensuite une classe "GestionnaireArrete" (par exemple) qui se structure sous une forme proche de
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class GestionnaireArrete
{
public:
/* les alias qui permettent d'utiliser notre gestionnaire comme les
* coneteneurs classiques ;)
*/
typedef std::set<Arrete>::iterator iterator;
typedef std::set<Arrete>::const_iterator const_iterator;
GestionnaireArrete(){}//rien à faire
~GestionnaireArrete(){}//sympa, tout se fait automatiquement ;)
void insertArrete(const Arrete&); // pourrait renvoyer l'arrete ;)
iterator& begin(); //pour obtenir la première arrete
iterator& end(); //quand on arrive à end, on a vu toutes les arretes ;)
iterator& operator++();//permet de passer à l'élément suivant
private:
std::set<Arrete> allar;//va contenir toutes les arretes ;)
iterator ite;
}; |
La méthode intéressante est insertArrete car pour begin(), il suffit d'initialiser ite à allar.begin() et de renvoyer it, pour end(), il suffit de renvoyer allar.end(), et, pour operator++, il suffit d'incrémenter ite et de le renvoyer (rien de particulier, en somme )
Toi, tu voudrais qu'avec deux points (p1 et p2, pour l'exemple), les arrêtes créées sous la forme de
1
2
| Arrete ar1=std::make_pair(p1,p2);
Arrete ar2=std::make_pair(p2,p1); |
soient considérées comme étant identiques 
La solution est relativement simple: dans la méthode insertArrete, il *suffit* de vérifier la présence de la permutation (autrement dit d'une arrête [p2,p1] pour ar1 ou d'une arrete [p1,p2] pour ar2
Cela peut se faire très facilement en implémentant la méthode sous la forme de
1
2
3
4
5
| void GestionnaireArrete:: insertArrete(const Arrete& toadd)
{
if(allar.find(std::make_pair(toadd.second,toadd.first))==allar.end())
allar.insert(toadd);
} |
ou, si tu préfères un code un peu plus verbeux sous la forme de
1
2
3
4
5
6
7
8
| void GestionnaireArrete:: insertArrete(const Arrete& toadd)
{
/* création de l'arrête "permutée" */
Arrete temp=std::make_pair(toadd.second, toadd.first);
/* on insere l'orginal si on ne trouve pas la permutation */
if(allar.find(temp)==allar.end())
allar.insert(toadd);
} |
En quelques lignes à peine, tu obtiens quelque chose qui sera sans doute bien plus efficace que ton HeapSort
Utilisation de la fonction HeapSort (algorithme de tri)
Répondre avec citation
A méditer: La solution la plus simple est toujours la moins compliquée
", ton point pourra servir comme clé dans un conteneur associatif 
Envoyé par Butterfly83
Partager