Discussion :

[ggvert]

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

J'ai une classe Coordonnée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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).



si vous pouviez m'aider, merci.

[therwald]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[gbdivers]

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 ?

[JolyLoic]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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