Intermittent "Vector iterator not dereferencable"

Question

I have the following code, but when I run it, I intermittently get a Debug Assertion Failed error, with the reason "vector iterator not dereferencable".

What I'm trying to do with the program is create a bunch of 2D shapes (squares and circles), then move them about one by one, checking for collisions as they go. When two shapes collide, I want them to be removed, until there is (at most) one shape remaining. About 1 in 3 attempts results in a successful outcome, where the program finds four collisions, then stops. Other times, it will find 1-3 collisions and then error.

I should also mention that I'm relatively new to C++ (and yes, this is a coursework assignment), so if there are any other rookie mistakes in my code, please do point them out!

My methods for moving and colliding seem fine on their own, so I've not included them here.

Square * s1 = new Square(seedCoord(limit), seedCoord(limit), 2.0);
... //There is 9 new shapes created here (squares and circles)

std::vector<Shape*> shape;
shape.push_back(s1);
... //All 9 shapes added to the vector

int m = shape.size();
bool collision = false;

while(m>1) //Keep running until only one shape hasn't collided
{       
    for (auto i=shape.begin(); i!=(shape.end());) //Perform move on each shape in sequence
    {   
        collision = false; //Set collision boolean to false

        (*i)->move(seedCoord(0.5), direction[(rand() % 4)], limit); //Perform move on shape

        for (auto j=shape.begin(); j!=(shape.end()-1);) //Check for collision with each shape in sequence
        {
            if((*i) != (*j)) //Ignore self when checking for collision
            {
                if((*i)->collide(*j)) //Check for collision
                {
                    std::cout << "Collision between " << (*i) << " and " << (*j) << "\n";
                    m=m-2; //Lower shapes count by two (ie remove two collided shapes)
                    delete *i; //Delete pointer to initial shape
                    i = shape.erase(i); //Erase shape object
                    delete *j; //Delete pointer to collided shape
                    j = shape.erase(j); //Erase shape object
                    collision = true; //Set collision boolean to true
                    break; //Break out of internal for-loop (shape has been deleted so no more checks are necessary)
                }
                else
                {
                    j++; //If no collision, move onto next shape
                }
            }
            else
            {
                j++; //If i=j, move onto next shape
            }
        }
        if(!collision) //If no collision with any shape, move onto next shape
        {
            i++; //If no collision with any shape, move onto next shape
        }
        else
        {
            break; //If collision has occurred, break out of external for-loop (shape has been deleted so no more checks are necessary)
        }
    }
}

Answer 1

Quoting cpprefernce on erase:

Iterators and references to the erased elements and to the elements between them and the end of the container are invalidated. The past-the-end iterator is also invalidated.

My guess is that your problem occurs when in your second call to erase(j), j is an iterator referring to a location between i and shape.end() and got invalidated.

Answer 2

You are running with two iterators over the same vector. When you erase an element of that vector, all iterators past that element are invalidated. That means that on each collision either i or j is invalidated as erase is called for the other one.

You continue to use the iterators after the erase. This gives undefined behavior, meaning "anything can happen". That "aything" means it can work most of the times, but there are times when it won't. Consider this case:

The last two elements collide, i is end()-2, j is end()-1. First you erase(i), meaning all elements get shoved one to the left, including the one j pointed to. j is now conceptually invalid, but being not much more than a pointer, it points now one past the last element, i.e. j == end(). You now go on and call delete *j;, dereferencing the end() iterator wich will trigger the assertion.

Answer 3

Looking at the code more closely, it looks like your issue is due to the erasure of elements

Namely

i = shape.erase(i); //Erase shape object
...
j = shape.erase(j); //Erase shape object

Now you're correctly using the newly returned iterator from vector.erase() but the problem is that i and j are both iterators into the same vector. This means the following happens

• 'i' is erased from the shape vector
• shape vector gets reallocated without the 'i' element
• 'i' is reassigned to the next element, within the vector's memory block (which has had the remaining elements after i shuffled down a position)
• 'j' is still pointing at the old memory location (not taking into account the shuffling)
• 'j' is erased from shape vector (which is potentially now after the last element)
• out of bounds error

Instead of deleting the elements within the loop, you'd be better off flagging your elements as 'dead' within the body of the loop, then using std::remove_if right at the end of the while loop

shape.erase(std::remove_if(shape.begin(), 
                           shape.end(),
                           isDead),
                           shape.end());

where isDead is a functor defined something like:

struct isDead 
{
    bool operator()(const Shape* pX) const 
    {
        return pX->isDead();
    }
};