Jump to content
  • Advertisement
Sign in to follow this  
Storyyeller

Adding to a vector while iterating through it?

This topic is 3345 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In my game, I maintain a vector of all currently active entities and iterate through them on each tick to update them. Unfortunately, my boss sometimes spawns projectiles when updated, which naturally get push_backed onto the vector. And the program sometimes crashes when this happens. I figured that push_back would not invalidate iterators to existing elements, but apparently this is not the case. It looks like dereferencing the now invalid iterator is the cause of the crashes. So what can I do? Is there some trick or design pattern I can use? Do I need to switch from vectors to lists?
    //Update Entities
    for(std::vector<boost::shared_ptr<Entity> >::iterator iter = myentities.begin(); iter != myentities.end(); ++iter)
    {
        (*iter)->Update(); 

        if (!(*iter)->Active())
        {
            (*iter).reset(); //Resets the smart pointer to null, thus hopefully destroying the object it pointed too
            iter = myentities.erase(iter); //Removes the now null pointer from the vector
            --iter; //Otherwise the element after the erased object would be skipped
        }
    }




Share this post


Link to post
Share on other sites
Advertisement
push_back() may or may not invalidate existing iterators. There are some things you can do to gain some control over this behavior, but IMO it's usually not worth the trouble.

Similarly, it's usually not worth the trouble (again, IMO) to add or remove elements from a container while iterating over it. Again, it can be done, but as you're discovering, it can be problematic.

Fortunately, there are some common idioms you can use here. For example, for adding new entities, you can accumulate any 'add entity' requests your entities might make while iterating over the container, and then process the requests separately in one go.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Fortunately, there are some common idioms you can use here. For example, for adding new entities, you can accumulate any 'add entity' requests your entities might make while iterating over the container, and then process the requests separately in one go.
The same can be done for removal requests, of course - gather them into a separate list and remove them all in one go.

Share this post


Link to post
Share on other sites
I tried the method of creating a separate vector for pending additions, and it works perfectly.

I just got another question.
Why can't I do this?


class Colossus
{
const static double PHASE1_HEALTH = 2;
const static double PHASE2_HEALTH = 3;
const static double MAXHEALTH = PHASE1_HEALTH+PHASE2_HEALTH;
}



I thought that using const variables would be better then #defines, due to type safety and being limited to class scope, but I am not sure why it won't let me define constants in terms of other constants.

Share this post


Link to post
Share on other sites
I think that's bad to begin with. Don't do it! I think you should make a colossus type that simply has a max life, phase 1 life, and phase 2 life - all of which are loaded from a file.

This makes your game very flexible in that you can have different types of coloussi without remaking new classes, it allows different circumstances that increase max hp, etc. But ya, simply doing it via functions will solve everything..

int getPhase1Hp(){return 2;}
int getPhase2Hp(){return 3;}
int getMaxHp(){return getPhase2Hp() + getPhase1Hp();}

Share this post


Link to post
Share on other sites
Quote:
Original post by Crazyfool
*** Snip ***
Um...did you reply to the wrong thread, perhaps? :S

@The OP: When I replied earlier, I didn't notice what you were actually doing in your code. As Codeka pointed out, in addition to adding new entities in a separate pass, you can also remove inactive entities in a separate pass, which will further simplify your code. An effective way to do this is the erase-remove idiom.

Also, in your code, it's redundant to call reset() before you remove the item. The call to erase() will destroy the smart pointer, at which point the pointed-at object will be destroyed (not 'hopefully' destroyed :-) if the reference count has dropped to zero.

There actually is an idiom for iterating and removing at the same time, but it's a little different than what you have; instead of trying to 'correct for' the incrementing of the iterator, you instead only increment the iterator if the item was not removed. (However, I'd still recommend using the erase-remove idiom instead of removing the items 'manually'.)

Share this post


Link to post
Share on other sites
Is this the correct way to do it?

bool predicate_IsInactive(entity_sptr argptr) {return !(argptr->Active());}

void PhysicsTick()
{
//Update Entities
for(std::vector<entity_sptr>::iterator iter = myentities.begin(); iter != myentities.end(); ++iter)
{
(*iter)->Update();
}
//Remove inactive entities
myentities.erase( remove_if(myentities.begin(), myentities.end(), predicate_IsInactive), myentities.end() );

//Add newly created entities to the main list
for(std::vector<entity_sptr>::iterator iter = newentities.begin(); iter != newentities.end(); ++iter)
{
myentities.push_back((*iter));
}
newentities.clear();

//... do other stuff




Quote:
Original post by Crazyfool
I think that's bad to begin with. Don't do it! I think you should make a colossus type that simply has a max life, phase 1 life, and phase 2 life - all of which are loaded from a file.

This makes your game very flexible in that you can have different types of coloussi without remaking new classes, it allows different circumstances that increase max hp, etc.


I figured that with an open ended project, it's better to hard code things at the start and refactor as necessary. I can understand doing stuff like that in a large project where you already know exactly what you are going to do, but for me, implementing a data file loading scheme and scripting language seems a bit premature when I don't even have a playable beta yet.
Why worry about supporting hypothetical future expansions when you aren't even sure what those are going to be? Isn't it better to figure out which code you commonly reuse as you actually expand, and redesign it as necessary then?

Share this post


Link to post
Share on other sites
Quote:
Original post by Storyyeller
Is this the correct way to do it?
*** Source Snippet Removed ***
I don't see anything wrong - looks like you have the right idea :)

I would probably call the function something other than PhysicsTick() though (since it obviously does more than that). Also, although the code looks fine, there are a few things you could do to make it more elegant, readable, and compact. A few things you might look into:

1. Using std::for_each() and boost::bind instead of writing out the update loop manually.

2. Using boost::bind in place of the 'is inactive' predicate.

3. Making the return value of the update function the condition for removal, and then using the update function as the predicate for remove_if().

4. Using vector::insert() rather than adding the new entities one at a time.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!