Supprimer doublons dans un vector

bonjour, voici le problème auquel je suis confronté.

J'ai une classe Coordonnée :

Code:

---

1 2 3 4 5 6 7

class Coordonees { private: int x; int y; };

---

dans une méthode d'une autre classe, j'ai un vector de coordonnée contenant des doubles (double au sens : même couple de X et Y). Je souhaite donc les supprimer.

Mon code :

Code:

---

1 2 3 4 5 6 7

for(int a = 0; a < retour.size() ; a++){ for(int b = a+1; b < retour.size() ; b++){ if((retour[a].getX()) == (retour[b].getX()) && ((retour[a].getY()) == (retour[b].getY()))) { retour.erase(retour.begin() + b); } } }

---

retour étant le vector.

Si je n'utilise pas ce code, le vector contient une vingtaine de Coordonnée, alors qu'avec le code il n'y en a plus que 8 que voici. Malheureusement comme on peut le constater, des doubles persistent (ici il y a trois fois le couple 6 et 6).

http://nsa25.casimages.com/img/2011/...5523381246.png

si vous pouviez m'aider, merci.

A mon avis, le problème est que si deux doublons se suivent, alors vous sautez le second car la délétion décale tous les indices. Un exemple en remplacant les couples par des lettres pour simplifier:

Code:

---

1 2 3

indices: 0 1 2 3 4 5 6 7 8 contenus: a b c d e f f f z

---

quand a=5, vous comparez avec l'indice b=6: c'est un doublon => vous l'effacez donc tout se décale d'un cran vers la gauche:

Code:

---

1 2 3

indices: 0 1 2 3 4 5 6 7 contenus: a b c d e f f z

---

cependant, l'itération se poursuit et la valeur de b est passée à l'indice 7, donc le doublon qui est passé de l'indice 7 à l'indice 6 à cause de l'effacement du premier doublon n'est jamais testé et reste...:aie:

Ne serait-il pas intéressant d'utiliser un conteneur de type set ou map si tu ne veux pas de duplicata de tes données ?

Ton algorithme est en O(n²), alors qu'on peut faire un O(n log n) : Commence par trier les données, puis ensuite enlève les doublons.

Un truc genre :

Code:

---

1 2	std::sort(retour.begin(), retour.end()); retour.erase(std::unique(retour.begin(), retour.end()), retour.end());

---