std::set - Bleiben Iteratoren erhalten?



  • Hallo Forum,

    wenn ich aus einem std::set etwas lösche oder neue Einträge hinzufüge, bleiben die übrigen Iteratoren dann erhalten?

    #include <set>
    #include <iostream>
    
    int main() {
        typedef std::set<int> MySet;
    
        MySet ms;
        ms.insert(1);
        ms.insert(5);
        ms.insert(8);
        ms.insert(3);
        ms.insert(9);
    
        MySet::iterator it = ms.find(8); // Iterator auf "8"
        ms.erase(ms.find(3));            // "3" löschen
    
        std::cout << *it << std::endl;   // Ist das noch möglich?
        it++;                            // Zeigt der Iterator nun auf "9"?
    }
    

    Das funktioniert auf jeden Fall mit VC, aber ist das auch so ISO-Standard?

    Grüße,

    daersc


  • Mod

    daersc schrieb:

    wenn ich aus einem std::set etwas lösche oder neue Einträge hinzufüge, bleiben die übrigen Iteratoren dann erhalten?

    Ja.



  • Du hast doch den Code schon, wär ja auch leicht zu testen, kurz kompilieren und schon weiß mans 😉

    Gruß freeG



  • fr33g schrieb:

    Du hast doch den Code schon, wär ja auch leicht zu testen, kurz kompilieren und schon weiß mans 😉

    daersc schrieb:

    Das funktioniert auf jeden Fall mit VC, aber ist das auch so ISO-Standard?

    Jap, hab ich ja auch 😉



  • fr33g schrieb:

    Du hast doch den Code schon, wär ja auch leicht zu testen, kurz kompilieren und schon weiß mans 😉

    Mit diesem Vorgehen wirst du früher oder später Probleme haben. Zumindest wenn du deine Projekte nicht auf einen einzigen Compiler beschränken möchtest.



  • fr33g schrieb:

    Du hast doch den Code schon, wär ja auch leicht zu testen, kurz kompilieren und schon weiß mans 😉

    Das heißt gar nichts. Leite nicht das Verhalten Deiner C++ Implementierung als Garantie des ISO Standards ab. Das guckt man einfach nach ... entweder in einem schlauen Buch oder im Standard (bzw kostenlos zugänglicher Entwurf).



  • Ja sorry da muss ich mich entschuldigen, hab das überlesen, dass er es mit VC getestet hat.
    Und dass man sich nicht nur auf seinen Kompilier verlassen soll, stimmt auch, tut mir Leid für die Antwort:D 😉



  • @gelöscht: .. war die richtige Antwort im falschen Thread



  • Was pasieren wird, weiß ich nicht: Aber einige Gedanken von mir dazu: Der Standard schreibt nicht vor, wie Iteratoren implementiert werden (und auch die Sets selbst), sondern nur bestimmte Grenzen, in denen die Operationen von der Laufzeit liegen müssen. (Wenn ich da jetzt nichts verwechsel)

    Wenn man das Beispiel oben mit einem Vektor ausführt, und statt 8, den Iterator auf 9 sucht, dann klappt das Beispiel mit VC 2005 nicht mehr.

    Es wäre jetzt auch denkbar, dass es eine Implementation des Iterators eines Sets ähnlich zu der eines Vektors gäbe, und damit wäre dann der Iterator nicht mehr gültig.

    Grundsätzlich wäre ich vorsichtig mit Iteratoren, die vor der Veränderung eines Containers erstellt wurden. (Sicher nach Stroustup ist: it = find(...); tmp = it; --tmp; erase(it); ++tmp; // tmp zeigt jetzt auf das Element hinter dem gelöschten), bei allen anders bekommenen Iteratoren wäre ich vorsichtig.



  • thor42 schrieb:

    Der Standard schreibt nicht vor, wie Iteratoren implementiert werden (und auch die Sets selbst), sondern nur bestimmte Grenzen, in denen die Operationen von der Laufzeit liegen müssen. (Wenn ich da jetzt nichts verwechsel)

    Nun, es gibt schon ein bisschen mehr Angaben des C++-Standards an die Iteratoren und Container als nur Zeitkomplexitäten. Zum Beispiel:

    §23.1.2/8 (Associative Containers) schrieb:

    The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

    thor42 schrieb:

    Es wäre jetzt auch denkbar, dass es eine Implementation des Iterators eines Sets ähnlich zu der eines Vektors gäbe, und damit wäre dann der Iterator nicht mehr gültig.

    Nein, das wäre nicht denkbar. Allein schon weil es sich um verschiedene Iteratorkategorien handelt.

    thor42 schrieb:

    Grundsätzlich wäre ich vorsichtig mit Iteratoren, die vor der Veränderung eines Containers erstellt wurden. (Sicher nach Stroustup ist: it = find(...); tmp = it; --tmp; erase(it); ++tmp; // tmp zeigt jetzt auf das Element hinter dem gelöschten), bei allen anders bekommenen Iteratoren wäre ich vorsichtig.

    Statt

    it = c.find(...);
    tmp = it;
    --tmp;
    c.erase(it);
    ++tmp
    

    reicht bei einem assoziativen Container c ein

    it = c.find(...);
    c.erase(it++);
    


  • Nexus schrieb:

    thor42 schrieb:

    Der Standard schreibt nicht vor, wie Iteratoren implementiert werden (und auch die Sets selbst), sondern nur bestimmte Grenzen, in denen die Operationen von der Laufzeit liegen müssen. (Wenn ich da jetzt nichts verwechsel)

    Nun, es gibt schon ein bisschen mehr Angaben des C++-Standards an die Iteratoren und Container als nur Zeitkomplexitäten. Zum Beispiel:

    §23.1.2/8 (Associative Containers) schrieb:

    The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

    Ok, damit ist die Frage des Erstellers ja auch geklärt.

    Nexus schrieb:

    thor42 schrieb:

    Es wäre jetzt auch denkbar, dass es eine Implementation des Iterators eines Sets ähnlich zu der eines Vektors gäbe, und damit wäre dann der Iterator nicht mehr gültig.

    Nein, das wäre nicht denkbar. Allein schon weil es sich um verschiedene Iteratorkategorien handelt.

    Das würde trozdem nicht ausschließen, dass es ähnlich implementiert wäre und dadurch Iteratoren ungültig würden - Aber der Standard sagt das ja anders.

    Nexus schrieb:

    thor42 schrieb:

    Grundsätzlich wäre ich vorsichtig mit Iteratoren, die vor der Veränderung eines Containers erstellt wurden. (Sicher nach Stroustup ist: it = find(...); tmp = it; --tmp; erase(it); ++tmp; // tmp zeigt jetzt auf das Element hinter dem gelöschten), bei allen anders bekommenen Iteratoren wäre ich vorsichtig.

    Statt

    it = c.find(...);
    tmp = it;
    --tmp;
    c.erase(it);
    ++tmp
    

    reicht bei einem assoziativen Container c ein

    it = c.find(...);
    c.erase(it++);
    

    [/quote]

    Also, dass ist mit Sicherheit nicht portabel: Weil c.erase(it) macht it ungültig, und dann mit einem ungültigen Iterator weiterzuarbeiten ist laut Strousstrup undefiniert.



  • thor42 schrieb:

    Nexus schrieb:

    it = c.find(...);
    c.erase(it++);
    

    Also, dass ist mit Sicherheit nicht portabel: Weil c.erase(it) macht it ungültig, und dann mit einem ungültigen Iterator weiterzuarbeiten ist laut Strousstrup undefiniert.

    Falsch, it wird nicht ungültig. Der Iterator wird erhöht, und dessen alten Wert an erase() übergeben. Bei der Löschung zeigt it bereits auf das nächste Element.

    Die Schreibweise it++ ist ja im Grunde das Gleiche wie du mit dem temporären Objekt gemacht hast, nur viel übersichtlicher und flexibler, da z.B. kein vorhergehendes Element existieren muss.



  • Nexus schrieb:

    thor42 schrieb:

    Nexus schrieb:

    it = c.find(...);
    c.erase(it++);
    

    Also, dass ist mit Sicherheit nicht portabel: Weil c.erase(it) macht it ungültig, und dann mit einem ungültigen Iterator weiterzuarbeiten ist laut Strousstrup undefiniert.

    Falsch, it wird nicht ungültig. Der Iterator wird erhöht, und dessen alten Wert an erase() übergeben. Bei der Löschung zeigt it bereits auf das nächste Element.

    Die Schreibweise it++ ist ja im Grunde das Gleiche wie du mit dem temporären Objekt gemacht hast, nur viel übersichtlicher und flexibler, da z.B. kein vorhergehendes Element existieren muss.

    Also, soweit ich den Code verstehe, ist er gleichbedeutend mit:

    tmp = it;
    c.erase(it);
    tmp++;
    it = tmp;
    

    Sprich, es wird erst eine Kopie angelegt und diese Kopie wird dann hinterher erhöt, da aber tmp auf das gelöschte Element zeigt, ist dieser Iterator auch nach c.erase(...) ungültig und damit ist das ganze undefiniert...



  • So, grade nochmal im Strousstrup nachgeschaut:

    unter 6.2.2 steht unter anderem folgendes:

    v[i] = i++; // Undefiniertes Ergebnis
    

    Daraus lässt sich schließen, dass vom Standard nicht vorgesehen ist, ob zuerst inkrementiert wird und dann die Zuweisung erfolgt, oder ob erst die Zuweisung erfolgt. Übertragen auf das Beispiel oben: Es ist im C++ standard nicht definiert, ob zuerst erase aufgerufen wird, oder ob zuerst it++ aufgerufen wird und somit ist das Ergebnis undefiniert. (Es sei denn, ich habe jetzt etwas aus dem Standard übersehen, was in dem Kapitel nicht erwähnt wird)



  • Bevor eine Methode ausgeführt wird, werden zunächst alle Parameterexpressions evaluiert. Dementsprechend wird erst das Inkrement ausgeführt und danach erase aufgerufen.

    Also:

    auto tmp = it;
    ++it;
    c.erase(tmp);
    


  • Dein Beispiel da ist aber auch ein bisschen was andres. Im Fall von erase ist es definiert (Stichwort Sequence Point).



  • life schrieb:

    Bevor eine Methode ausgeführt wird, werden zunächst alle Parameterexpressions evaluiert. Dementsprechend wird erst das Inkrement ausgeführt und danach erase aufgerufen.

    Also:

    auto tmp = it;
    ++it;
    c.erase(tmp);
    

    Ok, wenn dem so ist, dann ist es ok.

    Und danke für das aufklären, wieder was gelernt.


Log in to reply