Problems with iterators

[Droopy]

So I have this problem with not being able to iterate over a vector in a nestled for-loop. Here's the nestled for-loop:

bool innerHit = false;
for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
{
Sprite* spriteOne = *outerIter;
for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend() && (!sprites.empty()); innerIter++)
{
Sprite* spriteTwo = *innerIter;
if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
{
spriteOne->collisionReaction(spriteTwo);
spriteTwo->collisionReaction(spriteOne);
spriteOne->collisionDestroy(sprites);
spriteTwo->collisionDestroy(sprites);
innerHit = true;
}
if (innerHit)
break;
}
}

What happens is, after having called the collisionDestroy-function and the program tries to execute the nest loop in the outer for-loop, it all crashes with the text "Expression: vector iterator not decrementable", which I understand is because the iterator will have already become useless. The question is: know this, how do I fix it? I can't seem to get a hang of it.

Here's the collisionDestroy-function (the collisionReaction does nothing but sets a few local variables):

void Enemy::collisionDestroy(std::vector<Sprite*>& sprites)
{
for (std::vector<Sprite*>::iterator iter = sprites.begin(); iter != sprites.end(); iter++)
{

Enemy* tmp = dynamic_cast<Enemy*>(*iter);
if (this == tmp && collisionType == 3 || collisionType == 1)
{
sprites.erase(iter);
break;
}
}
}

[Droopy]

And sorry for the lack of indentation.

[Paul McKenzie]

So I have this problem with not being able to iterate over a vector in a nestled for-loop. Here's the nestled for-loop:

1) Use code tags when posting code. The code you posted is almost unreadable.

2) Your post is plain C++, i.e. there is no use of MFC, ATL, or other technologies relevant to the usage of the Visual C++ compiler. It is straight C++, with a few types such as "Sprite" that we don't know about. Therefore it would have been relevant to post in the non-Visual C++ forum.

For everyone's benefit, here is your code, formatted using code tags:

bool innerHit = false;
for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
{
    Sprite* spriteOne = *outerIter;
    for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend() && (!sprites.empty()); innerIter++)
    {
        Sprite* spriteTwo = *innerIter;
        if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
       {
            spriteOne->collisionReaction(spriteTwo);
            spriteTwo->collisionReaction(spriteOne);
            spriteOne->collisionDestroy(sprites);
            spriteTwo->collisionDestroy(sprites);
            innerHit = true;
        }
        if (innerHit)
            break;
    }
}

There is no need to write loops like this if you know what the ultimate goal is when it comes to proper usage of containers. The way you rewrite this entire sequence is to use algorithms from the STL that alters the container in a safe way.

Here's the collisionDestroy

Here is the problem. It calls

std::vector<Sprite*>::erase()

which is a very big issue.

Let's start at the beginning:

for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)

The above has the issue of being inefficient and very hard to read. First, it would be a lot easier if you used typedef:

typedef std::vector<Sprite*> SpriteVector;
//...
for (SpriteVector::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); ++outerIter)

Note how we typedef'ed the vector, and we use pre-increment in the outerIter loop variable.

Now we see that you are erasing items in the vector while you're looping (see the item in red). Whenever I see this, I can bet you had to write this loop and your inner loop (which has the same sort of checking) 2, 3, 4, or more times to get working in some manner, all due to bugs being discovered. The goal, if possible, is to not write loops that erase items in a container while looping within the container. This is especially the case for a simple container such as vector. There are very few times when you need to erase elements in a vector while looping over the vector.

The way you go about doing erasures in a vector is to arrange the items in the vector so that the "erased" items appear at the end of the container, with an iterator pointing to the beginning of the erased items so that you can safely call erase() in a separate step starting at this iterator. Again, usage of remove_if() / erase or std::partition() and erase() is recommended.

The easiest way to overcome this is in your Sprite class, have a simple bool member variable that sets whether this sprite has been destroyed (make sure you initialize this variable when you create a sprite to false). Then just set this boolean to true in your collisionDestroy method -- do not erase the item in the vector -- in effect, you're delaying the real erasure of the items for later. In your other loops above, you skip over the ones that have this bool variable set to true -- that is much easier than figuring out what is empty and potentially accessing an invalid iterator. Now, you are no longer erasing items in the middle of the loop which means your loop constraints need no longer check for invalid iterators, since they will always be valid.

void Enemy::collisionDestroy(std::vector<Sprite*>& sprites)
{
    for (SpriteVector::iterator iter = sprites.begin(); iter != sprites.end(); ++iter)
    {
        Enemy* tmp = dynamic_cast<Enemy*>(*iter);
        if (this == tmp && collisionType == 3 || collisionType == 1)
        {
            tmp->hasCollided = true;
	    break;
	}
    }
}

I changed the code so that we no longer erase, but just set the boolean. But this can also be rewritten, again, using algorithms (and why did you need to cast to Enemy??)

void Enemy::collisionDestroy(SpriteVector& sprites)
{
    if ( collisionType == 1 || collisionType == 3)              
    {
        SpriteVector::iterator it = find(sprites.begin(), sprites.end(), this);
        if ( it != sprites.end() )
           it->hasCollided = true;  
     }
}

If the goal was to find the sprite that equaled "this", and then erase it, then the above code should work.

Then in a separate step afterwards, outside of all of these loops, you use the remove_if() / vector::erase idiom.

#include <algorithm>

bool hasCollided(Sprite* sprite)
{
   return sprite->isCollided();  // this is just a public "getter" for the hasCollided flag that was set earlier.
}
//...
void Enemy::RemoveCollided()
{
    sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
}

Problem solved, or at least, made easier. The above checks the vector and erases all the ones that have the "hasCollided" flag set to true. Basically, all I did was come up with a scheme to invalidate the item (setting a simple bool member), and then at the end, erase the invalidated items.

(Note that I am using C++ 98 features, and not C++ 11. If I knew you were using C++ 11 (or Visual Studio 2013), then the RemoveCollided would make use of lamda's in the remove_if() call instead of a separate function such as hasCollided).

Regards,

Paul McKenzie

[Droopy]

1) Use code tags when posting code. The code you posted is almost unreadable.

2) Your post is plain C++, i.e. there is no use of MFC, ATL, or other technologies relevant to the usage of the Visual C++ compiler. It is straight C++, with a few types such as "Sprite" that we don't know about. Therefore it would have been relevant to post in the non-Visual C++ forum.

For everyone's benefit, here is your code, formatted using code tags:

bool innerHit = false;
for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
{
    Sprite* spriteOne = *outerIter;
    for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend() && (!sprites.empty()); innerIter++)
    {
        Sprite* spriteTwo = *innerIter;
        if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
       {
            spriteOne->collisionReaction(spriteTwo);
            spriteTwo->collisionReaction(spriteOne);
            spriteOne->collisionDestroy(sprites);
            spriteTwo->collisionDestroy(sprites);
            innerHit = true;
        }
        if (innerHit)
            break;
    }
}

There is no need to write loops like this if you know what the ultimate goal is when it comes to proper usage of containers. The way you rewrite this entire sequence is to use algorithms from the STL that alters the container in a safe way.
Here is the problem. It calls

std::vector<Sprite*>::erase()

which is a very big issue.

Let's start at the beginning:

for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)

The above has the issue of being inefficient and very hard to read. First, it would be a lot easier if you used typedef:

typedef std::vector<Sprite*> SpriteVector;
//...
for (SpriteVector::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); ++outerIter)

Note how we typedef'ed the vector, and we use pre-increment in the outerIter loop variable.

Now we see that you are erasing items in the vector while you're looping (see the item in red). Whenever I see this, I can bet you had to write this loop and your inner loop (which has the same sort of checking) 2, 3, 4, or more times to get working in some manner, all due to bugs being discovered. The goal, if possible, is to not write loops that erase items in a container while looping within the container. This is especially the case for a simple container such as vector. There are very few times when you need to erase elements in a vector while looping over the vector.

The way you go about doing erasures in a vector is to arrange the items in the vector so that the "erased" items appear at the end of the container, with an iterator pointing to the beginning of the erased items so that you can safely call erase() in a separate step starting at this iterator. Again, usage of remove_if() / erase or std:artition() and erase() is recommended.

The easiest way to overcome this is in your Sprite class, have a simple bool member variable that sets whether this sprite has been destroyed (make sure you initialize this variable when you create a sprite to false). Then just set this boolean to true in your collisionDestroy method -- do not erase the item in the vector -- in effect, you're delaying the real erasure of the items for later. In your other loops above, you skip over the ones that have this bool variable set to true -- that is much easier than figuring out what is empty and potentially accessing an invalid iterator. Now, you are no longer erasing items in the middle of the loop which means your loop constraints need no longer check for invalid iterators, since they will always be valid.

void Enemy::collisionDestroy(std::vector<Sprite*>& sprites)
{
    for (SpriteVector::iterator iter = sprites.begin(); iter != sprites.end(); ++iter)
    {
        Enemy* tmp = dynamic_cast<Enemy*>(*iter);
        if (this == tmp && collisionType == 3 || collisionType == 1)
        {
            tmp->hasCollided = true;
	    break;
	}
    }
}

I changed the code so that we no longer erase, but just set the boolean. But this can also be rewritten, again, using algorithms (and why did you need to cast to Enemy??)

void Enemy::collisionDestroy(SpriteVector& sprites)
{
    if ( collisionType == 1 || collisionType == 3)              
    {
        SpriteVector::iterator it = find(sprites.begin(), sprites.end(), this);
        if ( it != sprites.end() )
           it->hasCollided = true;  
     }
}

If the goal was to find the sprite that equaled "this", and then erase it, then the above code should work.

Then in a separate step afterwards, outside of all of these loops, you use the remove_if() / vector::erase idiom.

#include <algorithm>

bool hasCollided(Sprite* sprite)
{
   return sprite->isCollided();  // this is just a public "getter" for the hasCollided flag that was set earlier.
}
//...
void Enemy::RemoveCollided()
{
    sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
}

Problem solved, or at least, made easier. The above checks the vector and erases all the ones that have the "hasCollided" flag set to true. Basically, all I did was come up with a scheme to invalidate the item (setting a simple bool member), and then at the end, erase the invalidated items.

(Note that I am using C++ 98 features, and not C++ 11. If I knew you were using C++ 11 (or Visual Studio 2013), then the RemoveCollided would make use of lamda's in the remove_if() call instead of a separate function such as hasCollided).

Regards,

Paul McKenzie

Thank you! For the record, i AM using Visual Studio 2013/C++11. What would you change knowing that?

[2kaud]

The basic problem, put simply, is that .erase() invalidates any iterators for that vector so shouldn't really be used within an iterator loop.

See http://www.cplusplus.com/reference/vector/vector/erase/

There are ways of making .erase work in an iterator loop but I won't detail them here as they are not recommended and can make code maintenance a nightmare. The method suggested by Paul is the way to go about this. Depending upon how the vector is used, you might not need to actually remove the elements, just have them marked as collided and other code can use hasCollided().

[Paul McKenzie]

There are ways of making .erase work in an iterator loop but I won't detail them here as they are not recommended and can make code maintenance a nightmare.

At one of my jobs, the programmers there were doing basically the same thing as the OP. They could never figure out how to erase from a vector while looping -- you should have seen the creative ways that were done, all would eventually fail. Things like jumping over invalidated iterators, reseating the iterator, all sorts of things that made it a nightmare to maintain and work consistently.

I introduced them to std::partition() and erase(), and all of those problems that were plaguing that part of the code (for months) became resolved in less than 5 minutes.

Regards,

Paul McKenzie

[2kaud]

At one of my jobs, the programmers there were doing basically the same thing as the OP. They could never figure out how to erase from a vector while looping -- you should have seen the creative ways that were done, all would eventually fail. Things like jumping over invalidated iterators, reseating the iterator, all sorts of things that made it a nightmare to maintain and work consistently.

I introduced them to std:artition() and erase(), and all of those problems that were plaguing that part of the code (for months) became resolved in less than 5 minutes.

...and the moral of the story is to know your STL algorithms!

PS I wish that c++ tutors and books would remember the STL and give all of it the coverage it deserves - not just vectors, maps and i/o streams if you're lucky.

[Paul McKenzie]

...and the moral of the story is to know your STL algorithms!

Since this is the Visual C++ forum, I would also like to mention that partition(), remove_if(), sort(), random_shuffle(), and most of the algorithms works for the MFC CArray class and all of the CxxxxArray container classes.

A lot of people think STL is just about containers, not realizing there are a whole lot of algorithm functions that work on sequences of data, regardless of how the sequence is stored (array, vector, CArray, etc.).

Regards,

Paul McKenzie

[Droopy]

Still not working. Now I get the following error: Error 1 error C3867: 'Sname::Engine::hasCollided': function call missing argument list; use '&Sname::Engine::hasCollided' to create a pointer to member c:\users\johan\documents\visual studio 2013\projects\project3\project3\engine.cpp 100 1 Project3

The loops now look like this:

bool innerHit = false;
for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end(); outerIter++)
{
	Sprite* spriteOne = *outerIter;
	for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend(); innerIter++)
	{
		Sprite* spriteTwo = *innerIter;
		if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
		{
			spriteOne->collisionReaction(sprites, spriteTwo);
			spriteTwo->collisionReaction(sprites, spriteOne);
			innerHit = true;
		}
	}
}
if (innerHit)
{
	sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
}

And then there's the hasCollided-function in the same class as the loops (the Engine-class):

bool Engine::hasCollided(Sprite* sprite)
{
	return sprite->getCollided();
}

The collisionReaction-function in Enemy (which enherits from Sprite) now looks like this:

void Enemy::collisionReaction(std::vector<Sprite*>& sprites, Sprite* other)
{
	std::vector<Sprite*>::iterator it = find(sprites.begin(), sprites.end(), this);
	if (it != sprites.end())
		(*it)->setCollided(true);
	}
}

Any idea...?

[Paul McKenzie]

Still not working. Now I get the following error: Error 1 error C3867: 'Sname::Engine::hasCollided': function call missing argument list; use '&Sname::Engine::hasCollided' to create a pointer to member

The function object as I've written needs to be a global or static function, not a non-static member function.

There is a way to get a non-static member function as part of the call, and that is to use std::mem_fun_ref to convert a pointer-to-member into a function object. It's a little advanced, but I will show you here:

if (innerHit)
{
   sprites.erase(remove_if(sprites.begin(), sprites.end(), std::mem_fun_ref(&Enemy::hasCollided)), sprites.end());
}

This now calls your member function Enemy::hasCollided for each one of the sprites. If you still want the function to be more "local" and were not using Visual Studio 2013, you could do this using this method:

if (innerHit)
{
   struct HasCollidedImpl { static bool HasCollided(Sprite* s) { return s->getCollided(); } };
   sprites.erase(remove_if(sprites.begin(), sprites.end(), &HasCollidedImpl::HasCollided), sprites.end());
}

The above creates a local struct with a static function that test for collision. You then feed the erase() function with the address of this function.

Since you are using Visual Studio 2013, C++ now supports lambda functions -- these are local functions that you plug directly into the algorithm call (similar to example above). The difference is that C++ officially supports this. I haven't used the lambda functions, but I believe this should work:

if (innerHit)
{
   sprites.erase(remove_if(sprites.begin(), sprites.end(), [](Sprite *s) { return s->getCollided(); }), sprites.end());
}

Note that the third argument to remove_if is an entire function body and not a pointer to a function or function object. The syntax is weird if you don't know lambda's, as they can have various options and can get advanced.

Regards,

Paul McKenzie

[Philip Nicoletti]

1) Some notes:

sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());

where sprites is a std::vector<Sprite*>

I assume that the elements of vector were created using new. If so, you
have a memory leak (unless I missed the delete somewhere)

2) You can use auto to declare the type of the loop variable:

for (auto iter = sprites.begin(); iter != sprites.end(); ++iter)

3) You can use range based for loops. Examples:

for (Sprite * p : sprites) {  }
for (auto p : sprites) { }
for (auto & p : sprites) { }
for (const Sprite * p : sprites) {  }

see http://msdn.microsoft.com/en-us/libr...v=vs.110).aspx

[Philip Nicoletti]

Generally, the functor (hasCollided in your code), is a stand-alone function, not a member
function (or it is a static member function). There is a syntax to use if it is a member
function (which I don't recall off the top of my head). I think that is what the

use '&Sname::Engine::hasCollided'

is stating.

[Droopy]

I changed it to:

if (innerHit)
{
	sprites.erase(remove_if(sprites.begin(), sprites.end(), &Sname::Engine::hasCollided), sprites.end());
}

Now it says:

Error 1 error C2064: term does not evaluate to a function taking 1 arguments c:\program files (x86)\microsoft visual studio 12.0\vc\include\algorithm 1758 1 Project3

[Philip Nicoletti]

I don't see a reason why you can not make it a stand-alone function
or a static member function.

[Droopy]

I just solved it! Thanks Philip

And also, thank you Paul McKenzie! You're seriously the coolest guy ever