🔒 Locked

std::vector iterator and erase problem

Started by hallgeir Jun 23, 2007 at 4:16 AM 9 replies 1.6k views

Original Post

Jun 23, 2007 at 4:16 AM

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. :)

ToohrVyk

238

ToohrVyk

Jun 23, 2007 at 4:26 AM

vector::erase returns the next valid iterator. Make sure you don't increment it before testing it.

hallgeir

Author

hallgeir

Jun 23, 2007 at 4:32 AM

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. :)

the_edd

115

the_edd

Jun 23, 2007 at 6:05 AM

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

hallgeir

Author

hallgeir

Jun 23, 2007 at 8:21 AM

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.

ToohrVyk

238

ToohrVyk

Jun 23, 2007 at 8:23 AM

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.

hallgeir

Author

hallgeir

Jun 23, 2007 at 8:31 AM

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. :)

Zahlman

257

Zahlman

Jun 23, 2007 at 11:57 AM

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.)