Vector iterator not decrementable

[Hashtg]

Hi,
I am using a vector to store sprites for a simple game. The code is mostly from a tutorial on basic windows game programming, and this particular section is a copy to help me understand the principle. The issue I am having is that while the code compiles, when the program is run, a debug error is flagged where the vector iterator is not decrementable.

After running tests and trying to debug the program, the issue seems to arise when a sprite is deleted from the vector. I have included the particular element of the program which deals with this below (it is used twice, once for killing the sprite mid-program and again upon quitting the program. The error happens both times).

void GameEngine::CleanupSprites()
{
//Incrementally remove every sprite in vector
	vector <Sprite*>::iterator siSprite;
	for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)
	{
		delete (*siSprite);
		m_vSprites.erase (siSprite);
		siSprite--;
	}
}

I think the error is due to the iterator being invalidated before it is decremented, and this also appeared to be the error when I stepped over this code during debug; however, I am not sure how to go about fixing this problem, as the code was lifted out of the tutorial in this section and the example program functions correctly.

I would be very appreciative for any help you could give.
Hash

[Computergeek01]

The "erase()" member function does this automatically, I'd say just use that. http://www.cplusplus.com/reference/stl/vector/erase/

[ne555]

¿what thing is automatic?

You may want to use vector< auto_ptr<Sprite> > so you don't need to worry about delete them.
¿why are you trying to decrement the iterator, just to increment it later? (the iterator is invalidated after erase)
Also you are clearing the vector by erasing its first element, that is O(n^2)

forall( X, member(X, m_vSprites), destroy(X) ),
m_vSprites.clear().

[Computergeek01]

@ ne555: The whole thing is done automatically by "erase()", on Line 5 the OP is setting his iterator to the begining of the vector, and deleting everything inside of it with a for loop. This can be done automatically with:

m_vSprites.erase(m_vSprites.begin(), m_vSprites.back());

EDIT: I put "m_vSprites.end()" where I should have put "m_vSprites.back()".

[ne555]

It should be m_vSprites.end(), as erase ask for two iterators.
That is what clear() does. However you still need to delete the raw pointers yourself.

[Hashtg]

That works well for that scenario, thanks.
It doesn't work for the other situation though as the iterator will be invalidated regardless. Is there a way to save the 'position' of the iterator through the vector?
Cheers, Hash.

[ne555]

Use the return value of erase()

[Hashtg]

Sorry, I forgot to refresh the page! :S

Below is what I have as a replacement for the code I posted above, but the issue I mentioned in my last post is still there.

void GameEngine::CleanupSprites()
{
//Incrementally remove every sprite from memory
	vector <Sprite*>::iterator siSprite;
	for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)
		delete (*siSprite);

//Remove the vector elements
	m_vSprites.erase (m_vSprites.begin(), m_vSprites.back());
}

Cheers, Hash.

[m4ster r0shi]

Does this compile? -> m_vSprites.erase(m_vSprites.begin(), m_vSprites.back());

It should really be -> m_vSprites.erase(m_vSprites.begin(), m_vSprites.end());

But, as ne555 said, you can simply write -> m_vSprites.clear();

Hashtg wrote:

but the issue I mentioned in my last post is still there

What's that issue?

[Hashtg]

Yeah it does compile, but I'll change it: I wasn't sure what to put - still fairly new! Thanks for all the help.

Well the program has an update function that has the option to remove a single sprite (for instance after a collision). The function uses the same problematic code while stepping through the vector elements.

The problem is that after deleting the sprite from the memory and removing the vector element I think the iterator is invalidated, breaking the program. I could make the function so that each time the kill action is encountered it restarts the iterator but that hardly seems an efficient method. Is there any way to save the 'position' of the iterator through the vector elements and then reapply the position to the iterator?

Cheers, Hash.


Edit:
I thought it might be useful to provide the function code:

void GameEngine::UpdateSprites()
{
	RECT					rcOldSpritePos;
	SPRITEACTION				saSpriteAction;
	vector <Sprite*>::iterator		siSprite;

//Incrementally check each vector entry
	for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)
	{
//Save the initial sprite position
		rcOldSpritePos = (*siSprite) ->GetPosition();

//Update the sprite
		saSpriteAction = (*siSprite) ->Update();

//Handle the SA_KILL sprite action
		if (saSpriteAction & SA_KILL)
		{
			delete (*siSprite);
			m_vSprites.erase (siSprite);
			siSprite--;
		}

//Check for collisions
		if (CheckSpriteCollision (*siSprite))
//If there is a collision, restore the initial position
			(*siSprite) ->SetPosition (rcOldSpritePos);
	}
}

[m4ster r0shi]

Hashtg wrote:

Well the program has an update function that has the option
to  remove  a  single  sprite  (for  instance  after  a  collision).

This sounds suspicious... You should load your resources when your game starts and
release  them when it ends. Why  would  you want to  release  a single sprite  during
the  game? What if you need to use that  particular  sprite  again? Will you  reload  it?

[Disch]

This sounds suspicious... You should load your resources when your game starts and
release  them when it ends.

Sprites are not resources. They're very lightweight (assuming this is SFML)

The question here, though, is why is he using pointers at all? Why not just have vector<Sprite> instead of vector<Sprite*>?


As for removing elements in a loop, you're doing it wrong.

// BAD - what you're doing:
for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)
{
  if(remove_sprite)
  {
    m_vSprites.erase(siSprite);
    siSprite--;  // EXPLODE - siSprite is invalid from the previous call to erase
  }
}

The correct way to do it is like this:

// GOOD
siSprite = m_vSprites.begin();
while(siSprite != m_vSprites.end())
{
  if(remove_sprite)
  {
    siSprite = m_vSprites.erase(siSprite);  // remove it, revalidate the iterator
  }
  else
    ++siSprite;  // otherwise, just increment it
}

EDIT:

A general rule of thumb is if you find yourself writing code to "undo" the incrementation in a for loop, you probably shouldn't be using a for loop.

[Hashtg]

The resources are all loaded, the sprites are being removed as they need to disappear, for instance if a bullet hits a wall.

As for why I'm using pointers, most of this is either from a walkthrough or example code... the 'siSprite--' did make me wonder, but I assumed the tutorial had a fairly efficient method.

@Dirsch: Quick question, what are the implications of using a 'vector <Sprite>' instead of a 'vector <Sprite*>'? Other than notation will they act in a simliar way?

Cheers, Hash.

[m4ster r0shi]

Disch wrote:

Sprites are not resources.

Aren't they? I don't mean to question your authority on this subject,
but it would  make much more sense  to me if the OP used the word
'Object' or 'Entity' instead  of 'Sprite' in this  particular  piece of code.

When I see/hear the word 'Sprite' I think of something like
this -> http://en.wikipedia.org/wiki/File:Sprite-example.gif

Using the OP's  example, you may have many  bullets (objects) in your game, but
you'll want to have only one in_game_bullet_image (sprite) which will be created
using an  image file (raw  resource). I would think of a  sprite as an  intermediate
resource that acts as a means of  making the raw  resource easier to manipulate.

[Disch]

Hashtg wrote:

Quick question, what are the implications of using a 'vector <Sprite>' instead of a 'vector <Sprite*>

vector<Sprite> stores the actual sprite data in the vector.
vector<Sprite*> only stores a pointer to the sprite in the vector.

Advantages to vector<Sprite>:
- Accessing individual sprites is faster*
- Memory is managed automatically for you (no need to delete)

Advantages to vector<Sprite*>:
- Allows you to create polymorphic sprites (if you are deriving classes from sf::Sprite)
- Resizing the vector / removing elements from the vector is faster*

* take "faster" with a grain of salt, because the difference will be miniscule.

So unless you're deriving your own classes from sf::Sprite and want them to behave polymorphically, there's little reason to use pointers here -- since pointers just make you have to manage the memory yourself (more prone to errors/mistakes/leaks).

m4ster r0shi wrote:

you may have many  bullets (objects) in your game, but
you'll want to have only one in_game_bullet_image (sprite) which will be created
using an  image file (raw  resource).

SFML uses different terminology.

The actual image is an sf::Image. That is a resource that should not be frequently copied/reconstructed.

An sf::Sprite is just like a rectangle with some attributes for color/rotation/position/etc. You typically use one sf::Sprite for each bullet, but all those sprites share the same sf::Image.

[m4ster r0shi]

I see.

In the object - sprite - image  relationship, my understanding is that
sprite is closer to image, while sfml's is that sprite is closer to object.

I could still argue  though that,  conceptually,  it would be  better to only have
four sf::Sprites, bullet_up, bullet_left, bullet_down, bullet_right, each pointing
to a  different  part of the same  sf::Image, but since, as you say, a  sf::Sprite
is  just a  bunch  of  primitives,  I  guess  it  wouldn't  make  a  real  difference.

EDIT: Am I using 'conceptually' wrong here? If yes, please tell me.

[Hashtg]

Ok thanks Disch, that's sorted the problem out now.