# std::vector iterator and erase problem

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

## 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 on other sites
vector::erase returns the next valid iterator. Make sure you don't increment it before testing it.

##### Share on other sites
Quote:
 Original post by ToohrVykvector::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 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 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 on other sites
Quote:
 Original post by ziggwarthAnd 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 on other sites
Quote:
 Original post by ToohrVykWhenever 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 on other sites
Quote:
 Original post by ziggwarthD'oh. I see it now. Thanks for the heads up. :)

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

Quote:
 Original post by Toohr_VykIterators 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 on other sites
Cheers Zahlman for the explanations and sample code. I got something to work on now. :)

Thanks :)

##### Share on other sites
Quote:
 Original post by Zahlmanbool operator()(const ParticlePtr& pp) const

[wink]

1. 1
2. 2
frob
16
3. 3
4. 4
5. 5
Rutin
10

• 18
• 13
• 14
• 76
• 22
• ### Forum Statistics

• Total Topics
632140
• Total Posts
3004355

×