Safely removing entries from an std::vector?

[conman420]

Hey I am having trouble with an asteroid game I am making, the way I have entity deletion set up is that when an entity wants to delete itself a flag is set that is then sent to the world on the next think. The world will then remove that entity from the std::vector of all the entities in the game, but this is causing a lot of crashes can anyone see the problem?

[cpp]
void cWorld::Think()
{
sf::Event Event;

std::vector<cBaseEntity*>::iterator i;

while (App.GetEvent(Event))
{
if (Event.Type == sf::Event::Closed)
App.Close();
for (i=Entities.begin(); i != Entities.end(); i++)
{
cBaseEntity *ent = *i;
ent->AppEvent(Event, GetApp());
}
if ((Event.Type == sf::Event::MouseButtonPressed) && (Event.MouseButton.Button == sf::Mouse::Button::Left))
{
cBullet *bul = new cBullet;
bul->SetPosition(mShip->GetPosition().x, mShip->GetPosition().y);
bul->GetOutline().SetRotation(mShip->GetOutline().GetRotation());
AddEntity(bul);
}
}

//Loop through all entities and think them

int AsteroidCount = 0;

for (i=Entities.begin(); i != Entities.end(); i++)
{
cBaseEntity *ent = *i;
if (ent->GetClass() == 2)
{
AsteroidCount++;
}
ent->Think(GetApp());

std::vector<cBaseEntity*>::iterator i2;
for (i2=Entities.begin(); i2 != Entities.end(); i2++)
{
cBaseEntity *ent2 = *i2;

sf::Vector2f e1_pos = ent->GetPosition();
sf::Vector2f e2_pos = ent2->GetPosition();
sf::Vector2f dist;
dist.x = e1_pos.x - e2_pos.x;
dist.y = e1_pos.y - e2_pos.y;

if (sqrt(dist.x*dist.x + dist.y*dist.y) < 10)
{
if ((ent->GetClass() == 2 && ent2->GetClass() == 3) || (ent->GetClass() == 3 && ent2->GetClass() == 2))
{
std::cout << "must delete\n";
ent->FlagForDeletion(true);
ent2->FlagForDeletion(true);
}
}
}

if (ent->ShouldDelete())
{
Entities.erase(i); // entities removed here!
}
}

if ((fLastSpawnAsteroid + 3 < cur.GetElapsedTime()) && (AsteroidCount < 10))
{
std::cout << "Making asteroid";
cAsteroid *ast = new cAsteroid;
AddEntity(ast);
//Entities.push_back(ast);
fLastSpawnAsteroid = cur.GetElapsedTime();
}
}

[/cpp]

I am guessing that this is because the iterator becomes invalid when you remove stuff but I can't think of a better way to do this. The error is just a generic fatal error message.

[ZeekyHBomb]

You might wanna use a std::list. It doesn't invalidate iterators and it's also faster for removing elements from the middle.
I don't know where that'd crash your code though. I can imagine it crashing when you delete the last entity of the list, as you've then surpassed the lists end, as such you should check that before erasing the entities.

You're also leaking memory. You're allocating via new, but never delete them.

Also, to get more info on the error, fire up the debugger.

[Spoco]

[URL]http://www.cplusplus.com/reference/stl/vector/erase/[/URL]

It returns the next position or end() if it was the last one, you should assign that to i.

[conman420]

Crashing is less frequent but still happens a lot of I shoot an asteroid. New code:

[cpp]
void cWorld::Think()
{
sf::Event Event;

std::list<cBaseEntity*>::iterator i;

while (App.GetEvent(Event))
{
if (Event.Type == sf::Event::Closed)
App.Close();
for (i=Entities.begin(); i != Entities.end(); i++)
{
cBaseEntity *ent = *i;
ent->AppEvent(Event, GetApp());
}
if ((Event.Type == sf::Event::MouseButtonPressed) && (Event.MouseButton.Button == sf::Mouse::Button::Left))
{
cBullet *bul = new cBullet;
bul->SetPosition(mShip->GetPosition().x, mShip->GetPosition().y);
bul->GetOutline().SetRotation(mShip->GetOutline().GetRotation());
AddEntity(bul);
}
}

//Loop through all entities and think them

int AsteroidCount = 0;

for (i=Entities.begin(); i != Entities.end(); i++)
{
cBaseEntity *ent = *i;
if (ent->GetClass() == 2)
{
AsteroidCount++;
}
ent->Think(GetApp());

std::list<cBaseEntity*>::iterator i2;
for (i2=Entities.begin(); i2 != Entities.end(); i2++)
{
cBaseEntity *ent2 = *i2;

sf::Vector2f e1_pos = ent->GetPosition();
sf::Vector2f e2_pos = ent2->GetPosition();
sf::Vector2f dist;
dist.x = e1_pos.x - e2_pos.x;
dist.y = e1_pos.y - e2_pos.y;

if (sqrt(dist.x*dist.x + dist.y*dist.y) < 20)
{
if ((ent->GetClass() == 2 && ent2->GetClass() == 3) || (ent->GetClass() == 3 && ent2->GetClass() == 2))
{
std::cout << "must delete\n";
ent->FlagForDeletion(true);
ent2->FlagForDeletion(true);
}
}
}

if (ent->ShouldDelete())
{
i = Entities.erase(i);
}
}

if ((fLastSpawnAsteroid + 3 < cur.GetElapsedTime()) && (AsteroidCount < 10))
{
std::cout << "Making asteroid";
cAsteroid *ast = new cAsteroid;
AddEntity(ast);
//Entities.push_back(ast);
fLastSpawnAsteroid = cur.GetElapsedTime();
}
}
[/cpp]

The debugger points to the 29th line. It seems if two entities want to delete in one frame the game crashes but I don't know why.

[ltkerr0r]

[QUOTE=conman420;22153233]Crashing is less frequent but still happens a lot of I shoot an asteroid. New code:

[cpp]
void cWorld::Think()
{
sf::Event Event;

std::list<cBaseEntity*>::iterator i;

while (App.GetEvent(Event))
{
if (Event.Type == sf::Event::Closed)
App.Close();
for (i=Entities.begin(); i != Entities.end(); i++)
{
cBaseEntity *ent = *i;
ent->AppEvent(Event, GetApp());
}
if ((Event.Type == sf::Event::MouseButtonPressed) && (Event.MouseButton.Button == sf::Mouse::Button::Left))
{
cBullet *bul = new cBullet;
bul->SetPosition(mShip->GetPosition().x, mShip->GetPosition().y);
bul->GetOutline().SetRotation(mShip->GetOutline().GetRotation());
AddEntity(bul);
}
}

//Loop through all entities and think them

int AsteroidCount = 0;

for (i=Entities.begin(); i != Entities.end(); i++)
{
cBaseEntity *ent = *i;
if (ent->GetClass() == 2)
{
AsteroidCount++;
}
ent->Think(GetApp());

std::list<cBaseEntity*>::iterator i2;
for (i2=Entities.begin(); i2 != Entities.end(); i2++)
{
cBaseEntity *ent2 = *i2;

sf::Vector2f e1_pos = ent->GetPosition();
sf::Vector2f e2_pos = ent2->GetPosition();
sf::Vector2f dist;
dist.x = e1_pos.x - e2_pos.x;
dist.y = e1_pos.y - e2_pos.y;

if (sqrt(dist.x*dist.x + dist.y*dist.y) < 20)
{
if ((ent->GetClass() == 2 && ent2->GetClass() == 3) || (ent->GetClass() == 3 && ent2->GetClass() == 2))
{
std::cout << "must delete\n";
ent->FlagForDeletion(true);
ent2->FlagForDeletion(true);
}
}
}

if (ent->ShouldDelete())
{
i = Entities.erase(i);
}
}

if ((fLastSpawnAsteroid + 3 < cur.GetElapsedTime()) && (AsteroidCount < 10))
{
std::cout << "Making asteroid";
cAsteroid *ast = new cAsteroid;
AddEntity(ast);
//Entities.push_back(ast);
fLastSpawnAsteroid = cur.GetElapsedTime();
}
}
[/cpp]

The debugger points to the 29th line. It seems if two entities want to delete in one frame the game crashes but I don't know why.[/QUOTE]
I had this problem in a game recently too. It's because when you delete the first entity, the size of the vector is adjusted and any elements after that entity "move up" in their position. You then continue checking against the old Entities.end() which has changed. I solved the problem by traversing the vector from back to front so if I removed any items, only items that I already skipped over would have their indexes changed. I was using a for loop with no iterators.

[ZeekyHBomb]

I'd do
[cpp]if(ent->ShouldDelete())
{
delete ent; //free your memory !
if(Entities.erase(i) == Entities.end())
break;
}[/cpp]
And you can also make the distance more efficient by squaring the second arg instead of squarerooting the first arg.

[conman420]

Hmm I fixed it. Not the best solution but it works.

I basically added a new iterator called 'to_remove' when an entities wants to be deleted it sets to_remove to that entities place in the list. When the loop has finished executing it removes the entity that wanted to be removed. Of course this only allows on entity to be removed at a time but I don't think the several milliseconds it takes to remove an entity is going to pose a problem.

Thanks for pointing out my memory leaks to!