Sign in to follow this  
kfboelter

Small C++ list issue

Recommended Posts

So... I am having trouble in a small snippet of code, while dealing with a list... a list of particles...
Basically, here is the trouble:



void ParticleGenerator::idleUpdate()
{
for (it = particles.begin(); it != particles.end();it++)
{
(*it)->update();
if ((*it)->getTtl() < 0)
{
particles.erase(it);
break;
}

}
}






If I remove the "break" command, I get a weird error.. I suppose thats because the end of the list is not the same as it was when the loop started (given that I have one less element in there).

However, with the "break" command, particles start acting funny when the all start to get erased... they get too slow because I am constantly moving the iterator do the beginning of the list...
For sake of information, here is the non-idle update source (when a key is pressed, particles keep being added to the system.. actually, they are relocated to the origin position)



void ParticleGenerator::update()
{
for (it = particles.begin(); it != particles.end();it++)
{
(*it)->update();

if ((*it)->getTtl() < 0)
{
(*it)->restartParticle();
}
}
addParticle();
}






Anyone knows a way to solve this? I`m guessing that "break" does not belong there... not sure tho...

thanks

Share this post


Link to post
Share on other sites
erase() returns an iterator to the element after the one it erased, so the loop should look like this:


void ParticleGenerator::idleUpdate()
{
for (it = particles.begin(); it != particles.end();) // Removed it++
{
(*it)->update();
if ((*it)->getTtl() < 0)
it = particles.erase(it);
else
++it;
}
}

Share this post


Link to post
Share on other sites
Now that you've got the answer you wanted, is there a reason you're using a linked list here? Lists are notoriously inefficient when in comes to cache coherency during traversal, and in a particle system one generally has a lot of particles to iterate over and update. Since the order of updates is almost always irrelevant, a vector partitioned into 'live' and 'dead' segments is usually vastly more efficient.

You also appear to have a list of pointers-to-particles, which is going to hurt your coherency even more -- and it also suggests that you're leaking memory, because at least with the code you have shown you erase the pointer from the list without ever deleting it -- so unless something else manages the lifetime of the particle instances, you lose the reference to it and leak it.

Share this post


Link to post
Share on other sites
weeelll... thats sort of scary;;; hehe

You are suggesting that I'd be better off using a vector? I don't get the concept of 'live' and 'dead';;;

As fot the other part.. you suggest that I do not use a vetor of pointers? or should I just properly delete the pointers to the particles?

Share this post


Link to post
Share on other sites
I am suggesting you use: std::vector<Particle>

std::vector is a dynamic array, so all its elements will be next to each other in memory (compared to a linked list, where all the elements may be scattered all over memory) -- and I suggest using "Particle" instead of "Particle*" because that way you don't have to follow the pointer to get at the particle data -- if you are storing pointers, the actual data can be scattered all over memory anyhow so you don't gain much from using a vector. So you should just store the particles 'by value' in the vector.

What you'd have, basically, is a vector of Particle objects and an integer that represents the index of the first "dead" particle in the vector. When you process particles, you iterate through the vector until you get to the 'first dead object' index, and then you stop. When you have to remove a particle, rather than do so you just swap that particle with the last live particle. To "allocate" a new particle, just bump the partition index up by one and reset the state of that newly-available particle to the desired initial state.

Share this post


Link to post
Share on other sites
well.. just wanted to thank you, and tell that the vector<Particle> is working just fine... it has been some very enlightening information I just got in this thread.

thanks a lot. bye

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this