Iterator Invalidation in C++11/14 on Vector Erasure

Hi buddies!

How are you doing? I recently started working on another game for mobile platforms, in parallel with Breaking Fast. More news on that very soon, but today I want to share with you a problem that I found while working on a piece of code for that game.

At some point, I wanted to test whether I should remove a laser beam from a vector of laser beams. The context was something similar to the following:

 for (auto itLasers = mPlayerLasers.begin(); itLasers != mPlayerLasers.end(); ++itLasers)  
 {  
     for (auto itEnemies = mEnemies.begin(); itEnemies != mEnemies.end(); )  
     {  
       if (collide(*itLasers, *itEnemies))  
       {  
         itEnemies = mEnemies.erase(itEnemies);  
       } else  
       {  
         ++itEnemies;  
       }  
     } //end nested for  
 } //end outer for  

So basically, I tested every possible laser object against every possible enemy object. If a collision is detected, then I remove the enemy from the vector of enemies.

But wait: I have to remove the laser object that collided with the enemy as well. Assuming that a laser object can hit more than one enemy at a time (which is the behavior I want to implement), I cannot destroy the laser object until I'm done with iterating through all the enemies.

The proper solution is to have a boolean value that is set to false before entering the nested loop, and to set it to true when a collision is detected. Upon exiting the nested loop, we check this variable and update the next iterator accordingly (in the same way I update the itEnemies iterator).  This results in the following code:

 for (auto itLasers = mPlayerLasers.begin(); itLasers != mPlayerLasers.end(); )  
 {  
     bool collision = false;  
     for (auto itEnemies = mEnemies.begin(); itEnemies != mEnemies.end(); )  
     {  
       if (collide(*itLasers, *itEnemies))  
       {  
         collision = true;  
         itEnemies = mEnemies.erase(itEnemies);  
       } else  
       {  
         ++itEnemies;  
       }  
     } //end nested for  
     if (collision)   
     {  
      itLasers = mPlayerLasers.erase(itLasers);  
     } else   
     {  
      ++itLasers;  
     }  
 } //end outer for  

However, the first solution that I implemented was different, and led me to discover an error with iterators handling. This solution consisted of pushing the iterators of those lasers that collided in another vector. Then, after the loop, I would remove the elements of the vector. This is easier shown in code than explained:

 std::vector<std::vector<std::unique_ptr<LaserInfo>>::iterator> toDelete;  
 for (auto itLasers = mPlayerLasers.begin(); itLasers != mPlayerLasers.end(); ++itLasers)  
 {  
     for (auto itEnemies = mEnemies.begin(); itEnemies != mEnemies.end(); )  
     {  
       if (collide(*itLasers, *itEnemies))  
       {
         //Check that it's not already in the vector  
         if (std::find(toDelete.begin(), toDelete.end(), itLasers) == toDelete.end())  
         {  
           toDelete.push_back(itLasers);  
         }  
         itEnemies = mEnemies.erase(itEnemies);  
       } else  
       {  
         ++itEnemies;  
       }  
     } //end nested for  
 } //end outer for  
   
 for (auto it : toDelete)  
 {  
    mPlayerLasers.erase(it);  
 }  

However, and this is the point of this post, this is completely wrong! Why? Because, according to the C++ standard in relation to the erase method:

Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

This implies that when we call erase on it in the second loop, all subsequent iterators are invalidated and cannot be used to erase the rest of elements. f

But what happens if for some reason, we really need to defer the erasure of the laser elements? We can do it with a traditional index, as the following code illustrates: 

 std::vector<int> toDelete;  
 int index = 0;  
 for (auto itLasers = mPlayerLasers.begin(); itLasers != mPlayerLasers.end(); ++itLasers)  
 {  
     for (auto itEnemies = mEnemies.begin(); itEnemies != mEnemies.end(); )  
     {  
       if (collide(*itLasers, *itEnemies))  
       {  
         if (std::find(toDelete.begin(), toDelete.end(), index) == toDelete.end())  
         {  
           toDelete.push_back(index);  
         }  
         itEnemies = mEnemies.erase(itEnemies);  
       } else  
       {  
         ++itEnemies;  
       }  
     } //end nested for  
     ++index;  
 } //end outer for  
   
 int count = 0;  
 for (auto i : toDelete)  
 {  
   mPlayerLasers.erase(mPlayerLasers.begin() + i - count);  
   ++count;  
 }  

Now, we are storing the index of the laser to be removed in the toDelete vector. Then, during the second loop, we access the elements through the index. We need to consider all the elements that have been erased at each execution of the loop by using the count variable, because erase() relocates all the elements that go after the removed element, moving them one position to the left.

And that's all. See you soon!
FM