comportement d'un itérateur

Version imprimable

Bonjour à tous,
Comme exercice j'essaie d'écrire un générateur de nombres premiers à l'aide de la STL et d'itérateurs.
J'ai réussi à faire quelque chose qui fonctionne, mais il y a des détails qui m'ennuient.

Voici le programme:
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 39 40 #include <vector> #include <set> #include <iostream> using namespace std; int main() { int b; // obligé d'utiliser un set au lieu d'un vector pour s car on doit pouvoir supprimer des éléments au milieu du tableau. set<int> s; vector<int> t; // génère les prime jusque b b = 10; // on génère un set allant de 2 à b. for (int i = 2; i != b; i++) { s.insert(i); } int i = 0; while (s.size() != 0) { i++; cout << "Iteration = " << i << endl; t.push_back(*s.begin()); for (set<int>::iterator it = s.begin() ; it != s.end(); ++it) { cout << " s = " << *it << endl; if (*it % t.back() == 0) s.erase(it); } } cout << "++++++++++++++++++++++++++++" << endl; cout << "affichage des nombres premiers stockés dans le vecteur t" << endl; cout << "taille t = " << t.size() << endl; for (vector<int>::iterator it = t.begin() ; it != t.end(); ++it) { cout << "t = " << *it << endl; } return 0; }
Le résultat final est correct (le vecteur résultata contient 2, 3, 5, 7 comme prévu pour b=10). Mais voici la sortie :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Iteration = 1 s = 2 s = 3 s = 4 s = 3 s = 5 s = 6 s = 7 s = 8 s = 7 s = 9 Iteration = 2 s = 3 s = 5 s = 7 s = 9 s = 7 Iteration = 3 s = 5 s = 7 Iteration = 4 s = 7
Lors de l'itération 1, *it prend les valeurs 2, 3, 4 puis revient à 3. C'es là que je ne comprend pas comment fonctionne l'itérateur. Le problème vient a priori du fait que je modifie s dans le for et qu'on se mélange les pinceaux dans les adresses mémoires. Malheureusement je ne trouve pas d'explication sur ce qu'il se passe (je pense que lorsque je supprime un élement de s, ça décale tout vers la droite mais je ne comprend toujours pas pourquoi ça revient à 3 au lieu de passer à 5... Quelqu'un pourrait-il m'éclairer? :oops:

J'ai tenté ceci, mais ça ne solutionne pas le problème, il y a toujours un comportement bizarre...

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 <vector>
#include <set>
#include <iostream>

using namespace std;

int main() {
    int a,b;
    int nbr;
    vector<int> t;
    set<int> s;

    // on génère les prime jusque b
    b = 10;
    // on génère un set allant de 2 à b.
    for (int i = 2; i != b; i++)
    {
        s.insert(i);
    }
    int i = 0;
    while (s.size() != 0)
    {  i++;
        cout << "Iteration = " << i << endl;
        t.push_back(*s.begin());
        for (set<int>::iterator it = s.begin() ; it != s.end(); ++it)
        {
            cout << "       s  = " << *it << endl;
            if (*it % t.back() == 0) {s.erase(it); it++;}
            if (it == s.end()) break;
        }
    }
    cout << "++++++++++++++++++++++++++++" << endl;
    cout << "affichage des nombres premiers stockés dans le vecteur t" << endl;
    cout << "taille t = " << t.size() << endl;
    for (vector<int>::iterator it = t.begin() ; it != t.end(); ++it)
    {
        cout << "t = " << *it << endl;
    }

(les modifs en rouge: ajout de it++ après le s.erase() et break si on est à it = s.end())

sortie:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Iteration = 1
       s  = 2
       s  = 4
       s  = 5
       s  = 6
       s  = 8
       s  = 9
Iteration = 2
       s  = 3
       s  = 7
       s  = 9
Iteration = 3
       s  = 5
Iteration = 4
       s  = 7
++++++++++++++++++++++++++++
affichage des nombres premiers stockés dans le vecteur t
taille t = 4
t = 2
t = 3
t = 5
t = 7

03/12/2014, 10h25
fenkys

Bonjour,

Un iterator sur un set est invalidé en cas de deletion de l'élément indexé par l'itérateur.
Par ailleurs, tu peux faire un erase au milieu d'un vector. C'est juste moins efficace que pour d'autres containers.

Pour compenser ton problème d'itérateurs, il y a plusieurs solutions. L'une d'elle consiste à garder une copie de ton iterateur avant de l'itérer et de faire un erase sur la copie. Au passage, c'est ce que fait it++.

DOnc :

Citation:

if (*it % t.back() == 0) {s.erase(it++); }

Quant à cette ligne :

Citation:

if (it == s.end()) break;

Elle est inutile à ce stade de la boucle.

Cordialement
Fenkys
03/12/2014, 11h16
tiresias54

merci pour ta réponse :)

si je ne met pas le break, on part dans une boucle infinie (car - je crois - lorsqu'on supprime le dernier élément et qu'on itère, alors l'itérateur a dépassé la fin du set).
03/12/2014, 19h45
jo_link_noir

Normalement, erase() invalide seulement les itérateurs qui font référence à celui supprimer.
Depuis c++11 erase() retourne l'itérateur suivant it = s.erase(it).

En fait pour un set, la méthode s.erase met à jour l'itérateur en renvoyant le prochain élément (apparement ça n'est pas le même comportement pour un vector).

Au final ce code fonctionne parfaitement:

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
int main() {
    int b;
    vector<int> t;
    set<int> s;
 
    // on génère les prime jusque b
    b = 10;
    // on génère un set allant de 2 à b.
    for (int i = 2; i <= b ; i++)
    {
        s.insert(i);
    }
    while (s.size() != 0)
    {
        t.push_back(*s.begin());
        for (set<int>::iterator it = s.begin(); it != s.end();)
        {
            if (*it % t.back() == 0)
            {
                it = s.erase(it);
            }
            else
            {
                it++;
            }
        }
    }
    cout << "++++++++++++++++++++++++++++" << "\n";
    cout << "affichage des nombres premiers stockés dans le vecteur t" << "\n";
    cout << "taille t = " << t.size() << "\n";
    for (vector<int>::iterator it = t.begin() ; it != t.end(); ++it)
    {
        cout << "t = " << *it << "\n";
    }

je ne comprends cependant pas pourquoi

Code:

it = s.erase(it);

Code:

s.erase(it++);

n'est pas la même chose que

Code:

1
2
s.erase(it);
it++;

04/12/2014, 10h48
Bousk

Quand tu fais un erase, les itérateurs sont invalidés.
Tu incrémentes un itérateur invalidé, ça revient à appeler une méthode sur un objet que tu viens de delete.
Toutes les méthodes erase de la std (vector, set, list, ... - sauf celle de map dans sa version 99 je crois) retournent l'itérateur suivant. Pour pouvoir itérer justement.
04/12/2014, 11h17
tiresias54

Citation:

Envoyé par Bousk

Quand tu fais un erase, les itérateurs sont invalidés.
Tu incrémentes un itérateur invalidé, ça revient à appeler une méthode sur un objet que tu viens de delete.
Toutes les méthodes erase de la std (vector, set, list, ... - sauf celle de map dans sa version 99 je crois) retournent l'itérateur suivant. Pour pouvoir itérer justement.

Ah ok, donc a priori ce que j'avais mal compris c'est le fait que it n'est pas modifié par s.erase mais que par contre cette méthode renvoie un itérateur modifié :

si je fait s.erase(it++), le it sur lequel j'incrémente postfixé est celui qui est renvoyé par s.erase.
si je fait s.erase(); it++; le it sur lequel je travaille est le it invalidé lorsque s.erase() a été exécuté.
04/12/2014, 11h45
Bousk

En fait tu t'exprimes mal et confonds un peu trop de trucs.

Citation:

Envoyé par tiresias54

si je fait s.erase(it++), le it sur lequel j'incrémente postfixé est celui qui est renvoyé par s.erase.

Cette syntaxe ne fait rien d'autre que ce qui est écrit : utiliser la méthode erase sur l'objet s en passant en paramètre it que l'on post-incrémente.
L'ordre de résolution se fait en général de l'intérieur vers l'extérieur.
Donc on commence par post-incrémenter it.
L'opérateur ++ en suffixe fait incrémente la variable, puis retourne la valeur avant incrémentation.
Donc tu incrémentes it, qui passe sur un itérateur valide, puis tu erase sa valeur précédente.

Après faut juste lire les docs pour savoir quoi faire.
std::vector::erase t'indique clairement que tous les itérateurs après celui supprimés sont invalidés. Donc s.erase(it++); sera mauvais si s est un std::vector.
04/12/2014, 12h09
tiresias54

ok merci c'est plus clair :)
je met en résolu