IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C++ Discussion :

comportement d'un itérateur


Sujet :

C++

  1. #1
    Membre actif
    Profil pro
    ingénieur
    Inscrit en
    Novembre 2011
    Messages
    165
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur

    Informations forums :
    Inscription : Novembre 2011
    Messages : 165
    Points : 259
    Points
    259
    Par défaut comportement d'un itérateur
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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?

  2. #2
    Membre actif
    Profil pro
    ingénieur
    Inscrit en
    Novembre 2011
    Messages
    165
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur

    Informations forums :
    Inscription : Novembre 2011
    Messages : 165
    Points : 259
    Points
    259
    Par défaut
    J'ai tenté ceci, mais ça ne solutionne pas le problème, il y a toujours un comportement bizarre...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  3. #3
    Membre éprouvé Avatar de fenkys
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Octobre 2007
    Messages
    376
    Détails du profil
    Informations personnelles :
    Âge : 56
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : Octobre 2007
    Messages : 376
    Points : 1 054
    Points
    1 054
    Par défaut
    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 :
    if (*it % t.back() == 0) {s.erase(it++); }
    Quant à cette ligne :
    if (it == s.end()) break;
    Elle est inutile à ce stade de la boucle.


    Cordialement
    Fenkys

  4. #4
    Membre actif
    Profil pro
    ingénieur
    Inscrit en
    Novembre 2011
    Messages
    165
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur

    Informations forums :
    Inscription : Novembre 2011
    Messages : 165
    Points : 259
    Points
    259
    Par défaut
    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).

  5. #5
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    739
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2011
    Messages : 739
    Points : 3 627
    Points
    3 627
    Par défaut
    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).

  6. #6
    Membre actif
    Profil pro
    ingénieur
    Inscrit en
    Novembre 2011
    Messages
    165
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur

    Informations forums :
    Inscription : Novembre 2011
    Messages : 165
    Points : 259
    Points
    259
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

    ou
    n'est pas la même chose que


  7. #7
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    Juin 2010
    Messages
    7 113
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : Juin 2010
    Messages : 7 113
    Points : 32 958
    Points
    32 958
    Billets dans le blog
    4
    Par défaut
    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.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  8. #8
    Membre actif
    Profil pro
    ingénieur
    Inscrit en
    Novembre 2011
    Messages
    165
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur

    Informations forums :
    Inscription : Novembre 2011
    Messages : 165
    Points : 259
    Points
    259
    Par défaut
    Citation Envoyé par Bousk Voir le message
    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é.

  9. #9
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    Juin 2010
    Messages
    7 113
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : Juin 2010
    Messages : 7 113
    Points : 32 958
    Points
    32 958
    Billets dans le blog
    4
    Par défaut
    En fait tu t'exprimes mal et confonds un peu trop de trucs.
    Citation Envoyé par tiresias54 Voir le message
    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.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  10. #10
    Membre actif
    Profil pro
    ingénieur
    Inscrit en
    Novembre 2011
    Messages
    165
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : ingénieur

    Informations forums :
    Inscription : Novembre 2011
    Messages : 165
    Points : 259
    Points
    259
    Par défaut
    ok merci c'est plus clair
    je met en résolu

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Comprendre le comportement d’un Itérateur dans une liste
    Par achraf.b.a dans le forum Débuter
    Réponses: 9
    Dernier message: 16/01/2015, 15h52
  2. Comportement standard d'un itérateur avec un +=
    Par benlaug dans le forum C++/CLI
    Réponses: 3
    Dernier message: 01/12/2011, 11h46
  3. Réponses: 3
    Dernier message: 20/09/2006, 23h35
  4. Réponses: 2
    Dernier message: 22/09/2003, 12h23
  5. Copies de flots en passant par les itérateurs
    Par Christophe Brun dans le forum C++
    Réponses: 7
    Dernier message: 02/07/2003, 12h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo