Jump to content
  • Advertisement
Sign in to follow this  

std::vector iterator and erase problem

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

Hi. I've almost never used iterators in the past, so I came over a problem with probably a incredible simple solution, but I'm a bit stuck. The problem is this code:

typedef boost::shared_ptr<CParticle> ParticlePtr;
typedef std::vector<ParticlePtr> ParticleArray;

for (ParticleArray::iterator pItr = mParticles.begin(); pItr != mParticles.end(); ++pItr)
{
	(*pItr)->Update(Timefactor);

	if (!(*pItr)->IsAlive())
		mParticles.erase(pItr);
}

I'm guessing many can already see the problem, but I'll explain anyway: When I call the mParticles.erase(pItr) function, the iterator pItr "obviously" is set to NULL. When I then try to increase pItr when the loop continues, I get an assertion error: "Expression: ("this->_Mycont != NULL",0)". So how should I go on about erasing the current element from the std::vector array, without messing up the loop, when using iterators? Ps: I read that using iterators is the "preferred" way of going through the elements in a std::vector array.. which is why I've started looking into it in the first place. Is that true, and what advantages does it have? I don't mind using either way, I'm happy to learn whatever is "better". :P Thanks in advance. :)

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by ToohrVyk
vector::erase returns the next valid iterator. Make sure you don't increment it before testing it.


Ah I see. Thanks for a quick reply.

Cheers. :)

Share this post


Link to post
Share on other sites
Erasing elements from a vector invalidates all iterators into that vector.

In your case, the loop construct assumes that pItr will be valid, when it may not be after a call to mParticles.erase(pItr).

You really want something like:


typedef std::vector<ParticlePtr> ParticleArray;

ParticleArray::iterator pItr = mParticles.begin();

while (pItr != mParticles.end())
{
(*pItr)->Update(Timefactor);

if (!(*pItr)->IsAlive())
pItr = mParticles.erase(pItr);
else
++pItr;
}



But you should consider using the std::remove_if() algorithm and the erase() overload that takes an iterator range. It will likely be more efficient; removing elements from the middle of a vector is O(n) (think about how all the elements of the vector would have to be shuffled back one place to fill the 'gap').

Or you could keep the current algorithm and change to a std::list<>, in which case the removals will be O(1).

Edd

Share this post


Link to post
Share on other sites
I've changed my code a bit:

for (ParticleArray::iterator pItr = mParticles.begin(); pItr != mParticles.end(); ++pItr)
{
(*pItr)->Update(Timefactor);

if (!(*pItr)->IsAlive())
pItr = mParticles.erase(pItr);

if (pItr == mParticles.end())
break;
}




And it works it seems. Do anyone see a potential problem with this or should this be quite robust?

Also what is exactly the advantage of using iterators instead of just for (int i = 0; i < blablabla.size(); i++)? :)

Edit:
the_edd: Thanks, I will look into using a std::list. I've never used it before but I'll read up on it :)
I'm not sure if I understood the other option though (even if I remove a range of elements, wouldn't still the following elements have to be "moved"?)

Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by ziggwarth
And it works it seems. Do anyone see a potential problem with this or should this be quite robust?


Whenever it deletes an element, it skips the next one in row.

Quote:
Also what is exactly the advantage of using iterators instead of just for (int i = 0; i < blablabla.size(); i++)? :)


Iterators can be used with SC++L algorithms, such as the aforementioned std::remove_if and also work on containers without random access, such as lists.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Whenever it deletes an element, it skips the next one in row.


D'oh. I see it now. Thanks for the heads up. :)

The loop now looks like

ParticleArray::iterator pItr = mParticles.begin();

while (pItr != mParticles.end())
{
(*pItr)->Update(Timefactor);

if (!(*pItr)->IsAlive())
pItr = mParticles.erase(pItr);
else
++pItr;
}


which is pretty much what the_edd suggested.

Cheers for all the help. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by ziggwarth
D'oh. I see it now. Thanks for the heads up. :)


Quote:
Original post by the_edd
But you should consider using the std::remove_if() algorithm and the erase() overload that takes an iterator range.


Quote:
Original post by Toohr_Vyk
Iterators can be used with SC++L algorithms, such as the aforementioned std::remove_if



typedef boost::shared_ptr<CParticle> ParticlePtr;

struct ParticleUpdater {
double t;
ParticleUpdater(double t): t(t) {}
bool operator()(const ParticlePtr& pp) {
pp->Update(t);
return pp->IsAlive();
}
};

mParticles.erase(std::remove_if(mParticles.begin(), mParticles.end(), ParticleUpdater(Timefactor)), mParticles.end());



(It should also be possible to make this easier with boost::bind, boost::lambda or something else along those lines.)

Quote:
(even if I remove a range of elements, wouldn't still the following elements have to be "moved"?)


There are no "following elements" with this approach.

Because the standard library algorithms work with iterators rather than containers, they can't resize the containers themselves; therefore, std::remove_if effectively leaves garbage at the end of the container. The vector .erase() call simply trims off all the garbage at once. (You could also .resize(), but you'd have to convert the iterator returned by remove_if to an element count, and that's kind of messy.)

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!