Bonjour,  
 
Je construit une approximation d'une sphère, un icosaedre, en subdivisant ses faces(triangles), dans le but de l'afficher en opengl.
 
Le problème avec l'idée de subdivision c'est que des points sont créés en double (si on subdivise deux triangles qui ont en commun une arete, 3 points seront créés pour chaque triangle mais 2 de ces point auront la même position).
 
J'ai donc un conteneur qui contient l'ensemble des Points subdivisés.
A la création d'un nouveau point, si il n'existe pas un point ayant les même x, y et z , alors on insere le point , etc...
 
Le problème est qu'il ya beaucoup de point, et qu' avec un vector<Point*>, le parcours est très lent.
 
j'ai pensé à utiliser une multimap<float,Point*>
comme les points sont autour de l'origine, les x, y, z sont symétriques, donc j'ai utilisé la valeur absolue de x comme clé,
ca accelere le traitement pour les petites valeurs de subdivision, mais pour les très grandes, c'est très lent.
 
 
Quel conteneur utiliser pour ce type de probleme? merci

C'est le container le problème, vraiment ?
 
A priori les containers stl sont suffisamment bien codés, et tu peux leur faire confiance, pour que la complexité de l'algo de recherche soit la plus faible possible.
 
Peut etre que du coté de boost c'est mieux foutu, mais c'est pas évident.

STl est codé propre, c'est l'axiome n°1.
Revoit ton algo.

En fait j'aurai souhaité savoir quel conteneur de la STL serai le mieux adapté à mon problème ( par ex multimap, multiset, ...)

Concernant l'unicité des clefs, la map semble indiquée.
Mais jette un oeil du coté de boost tout de meme.

merci je vais voir, je connais pas trop boost

Evite tout de même d'utiliser un float comme clé, ça me paraît pas très sûr :s (si quelqu'un peut infirmer/confirmer...)

pourquoi pas un set<Point> ?
ou un set<Point*, PointComparator> si besoin de mémoire dynamique, où PointComparator est un Type foncteur capable de comparer deux points.
 
Un hash_set au lieu du set peut être envisager si tu as besoin de l'unicité et pas de l'ordre. Mais c'est une extension de la STL qui sera officialisée en 200x.

yes c'est ça qu'il me faut, je vais me renseigner sur le set<Point*, PointComparator>

 
Par exemple pour avoir un ordre strict sur un

Sous réserve que la comparaison de 2 float ait un sens sur ta machine.
 
PS : je nomme volontairement les paramètres a et b et pas left et right car l'operateur est complètement symétrique et commutatif, les deux paramètres n'ont pas besoin de recevoir un nom expressif.

moi je fais en général des map<vertex, int>, avec un comparateur lexicographique de vertex (avec un seuil sur la distance pour avoir un weld).
dans la classe qui s'occupe de l'indexation des vertexs, tu maintiens le nombre de vertex poussés.
et quand tu veux pousser/obtenir un vertex via son indice, si le vertex est trouvé dans la map tu l'as sinon, tu l'insère avec comme indice le compteur vertices et tu incrémente ce compteur.
 
tu as ainsi ta map avec tes couples vertexs/indices linéaires.
pour obtenir un buffer des vertices linéaires, t'as juste à balayer la collection du map, en émettant chaque vertex dans un std::vector<vertex> à la position associée.
 
et au final tu te retrouve avec un joli couple vertexbuffer/indexbuffer presque idéaux.  
 
reste plus qu'à réorganiser pour les triangles pour maximiser les réussites du cache post-T&L, et réorganiser les vertexs pour réduire les pages faults et augmenter le cache-hit sur le cache général.