Deleting elements from std set while iterating

Question

I need to go through a set and remove elements that meet a predefined criteria   This is the test code I wrote    include  lt set gt   include  lt algorithm gt   void printElement int value        std  cout  lt  lt  value  lt  lt          int main         int initNum       0  1  2  3  4  5  6  7  8  9        std  set lt int gt  numbers initNum  initNum   10          print  0 1 2 3 4 5 6 7 8 9      std  for each numbers begin    numbers end    printElement        std  set lt int gt   iterator it   numbers begin            iterate through the set and erase all even numbers     for    it    numbers end      it            int n    it          if  n   2    0                   wouldn t invalidate the iterator              numbers erase it                           print  1 3 5 7 9      std  for each numbers begin    numbers end    printElement        return 0      At first  I thought that erasing an element from the set while iterating through it would invalidate the iterator  and the increment at the for loop would have undefined behavior  Even though  I executed this test code and all went well  and I can t explain why   My question  Is this the defined behavior for std sets or is this implementation specific  I am using gcc 4 3 3 on ubuntu 10 04  32-bit version   by the way   Thanks   Proposed solution   Is this a correct way to iterate and erase elements from the set   while it    numbers end          int n    it      if  n   2    0               post-increment operator returns a copy  then increment         numbers erase it           else              pre-increment operator increments  then return           it            Edit  PREFERED SOLUTION  I came around a solution that seems more elegant to me  even though it does exactly the same   while it    numbers end             copy the current iterator then increment it     std  set lt int gt   iterator current   it        int n    current      if  n   2    0               don t invalidate iterator it  because it is already            pointing to the next element         numbers erase current             If there are several test conditions inside the while  each one of them must increment the iterator  I like this code better because the iterator is incremented only in one place  making the code less error-prone and more readable

User · Answer

C  20 will have  uniform container erasure   and you ll be able to write   std  erase if numbers     int n   return n   2    0       And that will work for vector  set  deque  etc  See cppReference for more info

User · Answer

I think using the STL method  remove if  from  could help to prevent some weird issue when trying to attempt to delete the object that is wrapped by the iterator   This solution may be less efficient   Let s say we have some kind of container  like vector or a list called m bullets   Bullet  Ptr is a shared pr lt Bullet gt     it  is the iterator that  remove if  returns  the third argument is a lambda function that is executed on every element of the container  Because the container contains Bullet  Ptr  the lambda function needs to get that type or a reference to that type  passed as an argument    auto it   std  remove if m bullets begin    m bullets end       Bullet  Ptr bullet          dead bullets need to be removed from the container     if   bullet- gt isAlive                 lambda function returns true  thus this element is  removed          return true            else             in the other case  that the bullet is still alive and we can do            stuff with it  like rendering and what not          bullet- gt render       while checking  we do render work at the same time            then we could either do another check or directly say that we don t            want the bullet to be removed          return false               The interesting part is  that all of those objects were not really    completely removed  as the space of the deleted objects does still     exist and needs to be removed if you do not want to manually fill it later     on with any other objects     erase dead bullets m bullets erase it  m bullets end        remove if  removes the container where the lambda function returned true and shifts that content to the beginning of the container  The  it  points to an undefined object that can be considered garbage  Objects from  it  to m bullets end   can be erased  as they occupy memory  but contain garbage  thus the  erase  method is called on that range

User · Answer

If you run your program through valgrind  you ll see a bunch of read errors   In other words  yes  the iterators are being invalidated  but you re getting lucky in your example  or really unlucky  as you re not seeing the negative effects of undefined behavior    One solution to this is to create a temporary iterator  increment the temp  delete the target iterator  then set the target to the temp   For example  re-write your loop as follows   std  set lt int gt   iterator it   numbers begin                                   std  set lt int gt   iterator tmp                                                      iterate through the set and erase all even numbers                        for     it    numbers end                                                                                                                                     int n    it                                                                  if  n   2    0                                                                                                                                                tmp   it                                                                       tmp                                                                        numbers erase it                                                             it   tmp                                                                                                                                              else                                                                                                                                                            it

User · Answer

Just to warn  that in case of a deque container  all solutions that check for the deque iterator equality to numbers end   will likely fail on gcc 4 8 4  Namely  erasing an element of the deque generally invalidates pointer to numbers end       include  lt iostream gt   include  lt deque gt   using namespace std  int main         deque lt int gt  numbers     numbers push back 0     numbers push back 1     numbers push back 2     numbers push back 3       numbers push back 4      deque lt int gt   iterator  it end   numbers end       for  deque lt int gt   iterator it   numbers begin    it    numbers end            if   it   2    0          cout  lt  lt   Erasing element     lt  lt   it  lt  lt    n         numbers erase it           if  it end    numbers end          cout  lt  lt   it end is still pointing to numbers end   n           else       cout  lt  lt   it end is not anymore pointing to numbers end   n                     else         cout  lt  lt   Skipping element     lt  lt   it  lt  lt    n           it                Output   Erasing element  0 it end is still pointing to numbers end   Skipping element  1 Erasing element  2 it end is not anymore pointing to numbers end     Note that while the deque transformation is correct in this particular case  the end pointer has been invalidated along the way  With the deque of a different size the error is more apparent   int main         deque lt int gt  numbers     numbers push back 0     numbers push back 1     numbers push back 2     numbers push back 3     numbers push back 4      deque lt int gt   iterator  it end   numbers end       for  deque lt int gt   iterator it   numbers begin    it    numbers end            if   it   2    0          cout  lt  lt   Erasing element     lt  lt   it  lt  lt    n         numbers erase it           if  it end    numbers end          cout  lt  lt   it end is still pointing to numbers end   n           else       cout  lt  lt   it end is not anymore pointing to numbers end   n                     else         cout  lt  lt   Skipping element     lt  lt   it  lt  lt    n           it                Output   Erasing element  0 it end is still pointing to numbers end   Skipping element  1 Erasing element  2 it end is still pointing to numbers end   Skipping element  3 Erasing element  4 it end is not anymore pointing to numbers end   Erasing element  0 it end is not anymore pointing to numbers end   Erasing element  0 it end is not anymore pointing to numbers end       Segmentation fault  core dumped    Here is one of the ways to fix this    include  lt iostream gt   include  lt deque gt   using namespace std  int main         deque lt int gt  numbers    bool done iterating   false     numbers push back 0     numbers push back 1     numbers push back 2     numbers push back 3     numbers push back 4      if   numbers empty          deque lt int gt   iterator it   numbers begin        while   done iterating          if  it   1    numbers end          done iterating   true                 if   it   2    0        cout  lt  lt   Erasing element     lt  lt   it  lt  lt    n         numbers erase it                   else       cout  lt  lt   Skipping element     lt  lt   it  lt  lt    n         it

User · Answer

I came across same old issue and found below code more understandable which is in a way per above solutions   std  set lt int  gt   iterator beginIt   listOfInts begin    while beginIt    listOfInts end             Use your member     std  cout lt  lt   beginIt  lt  lt std  endl          delete the object     delete   beginIt           erase item from vector     listOfInts erase beginIt            re-calculate the begin     beginIt   listOfInts begin

User · Answer

This behaviour is implementation specific  To guarantee the correctness of the iterator you should use  it   numbers erase it    statement if you need to delete the element and simply incerement iterator in other case

User · Answer

You misunderstand what  undefined behavior  means  Undefined behavior does not mean  if you do this  your program will crash or produce unexpected results   It means  if you do this  your program could crash or produce unexpected results   or do anything else  depending on your compiler  your operating system  the phase of the moon  etc   If something executes without crashing and behaves as you expect it to  that is not proof that it is not undefined behavior  All it proves is that its behavior happened to be as observed for that particular run after compiling with that particular compiler on that particular operating system   Erasing an element from a set invalidates the iterator to the erased element  Using an invalidated iterator is undefined behavior  It just so happened that the observed behavior was what you intended in this particular instance  it does not mean that the code is correct

User · Answer

This is implementation dependent   Standard 23 1 2 8      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    Maybe you could try this -- this is standard conforming   for  auto it   numbers begin    it    numbers end            if   it   2    0            numbers erase it               else             it            Note that it   is postfix  hence it passes the old position to erase  but first jumps to a newer one due to the operator   2015 10 27 update  C  11 has resolved the defect  iterator erase  const iterator position   return an iterator to the element that follows the last element removed  or set  end  if the last element was removed   So C  11 style is   for  auto it   numbers begin    it    numbers end            if   it   2    0            it   numbers erase it             else             it

[c++] Deleting elements from std::set while iterating

Examples related to c++

Examples related to iterator

Examples related to set

Examples related to std

Examples related to c++-standard-library