Jump to content
  • Advertisement
Sign in to follow this  
yeisnier

Iterating a potentially deletable list

This topic is 3832 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

I have a list of pointers to a class cUpdater that have an update method.
class cUpdater
{
   public:
       virtual Update()=0;
}

list<A*> lpUpdaters;

I want to iterate that list in my main loop and call the update method of the list. So far is easy:
for (list<cA*>::iterator iter(lpUpdaters.begin()); iter!=lpUpdaters.end(); ++iter)
   (*iter)->Update();

But the problem starts when inside the update method it removes the updater from the list. As an example, suppose I have a Player inheriting from cUpdater and in the Update method it founds that has being killed, so he remove itself from the list of Updaters. The problem is that after it returns from the update method the iterator is no longer valid (because it was removed) and the program crash. The next way make a temporal that solves the problem by moving to the next before it call the update method, so if it gets removed the iterator is still valid
list<cA*>::iterator iter, itemp
for (iter = lpUpdaters.begin(); iter!=lpUpdaters.end();)
{
   itemp = iter;
   iter++;
   (*itemp)->Update();
}

But there is another problem, what about if inside the Update method more than one updater is removed. Take for instance that the player removes itself from the list, plus all its allies. That is really a problem, because now the next iterator could not be valid when the updater returns. My question: How to implement the iteration of a list that call the Update method with the condition that inside the Update method new Updaters can be added or removed from the list? One solution is to each time I want to traverse the list to move them all to a temporal list and keep updating the first one and after that remove it until the list is empty. But that has the disadvantage of all the copies. As this is done several times per frame I need it to be fast. Is there any good way I'm missing?

Share this post


Link to post
Share on other sites
Advertisement
The safe, simple way (that's also easily extendible to be thread-safe):

//Header

class Entity
{
bool alive;

void Tick() {/*do stuff*/};
};

struct World
{
std::list<Entity*> entities;

void Tick();
void Garb();
};






#include <boost/foreach.hpp>
//Source
void World::Tick()
{
BOOST_FOREACH(Entity *e, entities)
{
if(e->Alive)
e->Tick();
}

Garb();
}

bool AliveOrKill(Entity *e)
{
if(!e->alive)
{
delete e;
return true;
}
return false;
}

void World::Garb()
{
entities.remove_if(AliveOrKill);
}



Share this post


Link to post
Share on other sites
Quote:
Original post by Hnefi
The safe, simple way (that's also easily extendible to be thread-safe):
*** Source Snippet Removed ***

*** Source Snippet Removed ***


You're using Boost for loop structures, but not for smart pointers or containers?! :)


class Entity {
bool alive;
public:
void Tick() {/*do stuff*/};
// This is possibly the easiest and simplest - though not shortest - way
// to deal with converting a data member into a free function for std::remove_if
friend bool dead(const Entity& e) { return !e.alive; }
};

struct World {
// Chances are good, from your description of what you're doing, that a
// ptr_container is a better fit for you than a container of smart pointers.
typedef boost::ptr_list<Entity> Entities;
Entities entities;

void Tick() {
Entities::iterator begin = entities.begin(), end = entities.end();
std::for_each(begin, end, std::mem_fun_ref(&Entity::tick));
entities.erase(std::remove_if(begin, end, dead), end);
}
};



It may be possible, depending on your situation, to collapse the "Tick" and 'dead' work together, and get rid of the data member, by letting Tick() return bool to indicate whether the object died this tick. It depends on what causes Entities to die.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
You're using Boost for loop structures, but not for smart pointers or containers?! :)

Well, we all have our eccentricities :). I've never bothered to get into smart pointers, because my use of pointers have never really mandated it. But I suppose some day I'll switch over.
Quote:
It may be possible, depending on your situation, to collapse the "Tick" and 'dead' work together, and get rid of the data member, by letting Tick() return bool to indicate whether the object died this tick. It depends on what causes Entities to die.

Indeed, it may, depending on several things. But I'm not quite sure I see the advantage of doing that. I'd be interested to hear your reasons for it.

Share this post


Link to post
Share on other sites
I think in the end you should live with the limitation of not modifying the list while using it. Then write some code that catchs cases where someone is modifying the list while your using it and have it assert. I made a templated list that hasa std::list inside it. In order to use it you must lock/unlock or it asserts. The final release is replaced by a std::list.

When you think of it, do you want to compilcate the iteration of the list to support something you likely shouldn't be doing? I also tag things like this to be destroyed.

If this still tastes bad, then you might want to use a vector of pointers and instead of removing, you set the pointer to NULL. It really depends on how often the list changes and how big it is.

Oh, another pattern is to have your Update return whether or not to delete the entity.

Share this post


Link to post
Share on other sites
Play it safe, make a copy of the list when your working on it, call it the work list, since its a local copy, the iterator won't become corrupt when u modifiy the update list externally.

Also you'll need to manage any ptr manually in C++, so be sure not to leave lingering ptr references around, unless you opt to use ref counting or other rsrc management schemes.



list<A*> copyUpdaters = lpUpdaters;

for (list<cA*>::iterator iter(copyUpdaters.begin()); iter!=copyUpdaters.end();++iter)
(*iter)->Update();




Good Luck!

-ddn

Share this post


Link to post
Share on other sites
Quote:
Original post by ddn3
Play it safe, make a copy of the list when your working on it, call it the work list, since its a local copy, the iterator won't become corrupt when u modifiy the update list externally.
This can be a good solution for some situations, and in this case it would certainly prevent the iterator becomming invalid, however, just because you've copied the container of pointers doesn't mean that as you iterate over those pointers that they all point to objects that haven't been deleted as previous items were updated.

This is either a job for reference-counted smart pointers, or
returning a bool to indicate object death, and if necessary setting a kill-bit in the other objects such that when they are next processed, they too will return true to be killed.

Share this post


Link to post
Share on other sites
If one Update triggers multiple deletes, you've got to use flagging and pruning, I don't think there's any other way. If you're deleting only the current element, and you have a doubly linked list (you can -- the iter) you could just do something like this:


for (iter = start; iter != end; ++iter)
{
if (iter->Update())
{
list.remove(iter);
--iter;
}
}


But the safest way to do it would be the first option. In C# and Java for example foreach statements will cause compilation errors when you modify the list you're looping on - and it's for a good reason. I'm actually wondering if you could do something like that in C++.

Share this post


Link to post
Share on other sites
I'm pretty sure that that's undefined behaviour. If you perform destructive operations on a container through an iterator, that iterator is no longer valid. Thus the line
--iter;
is bad juju. You can dodge the issue by assigning the iterator to the return value of the remove() function, but I'm not sure where that iterator will point to in the list.

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!