• Advertisement
Sign in to follow this  

Proper way to erase an element from a vector when iterating

This topic is 472 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've looked this up already and here (http://stackoverflow.com/questions/4645705/vector-erase-iterator) the answer is as such:

 

 

t the end of the loop ++iterator is always called, so you increment .end() which is not allowed.

Simply checking for .end() still leaves a bug though, as you always skip an element on every iteration (it gets 'incremented' by the return from .erase(), and then again by the loop)

 

 

So can someone explain why doing it this way is wrong?

vector<AnimatedBitmap*>::iterator thisIter;
		for (thisIter = allLoaded.begin(); thisIter < allLoaded.end(); thisIter++)
		{
			if ((*thisIter)->GetID() == this->mID)
				thisIter = allLoaded.erase(thisIter);

			if (thisIter == allLoaded.end())
				break;
		}

I don't see how we're skipping an element.

Share this post


Link to post
Share on other sites
Advertisement

When erase() gets called, the elements after the element you're erasing get shuffled down in memory. So:
 

// you go from this
1 2 3 4 5
^
iterator points at this element

// to this
1 2 4 5
^
iterator points at this element
Now your iterator is pointing at the next element after the element you erased.

You then increment the iterator in the for loop, resulting in this:
1 2 4 5
^
iterator points at this element
Oops, you skipped the element immediately after the one you erased.

The proper way to get around this is to only increment the iterator if you didn't erase an element, like so:
// also, using auto and != not < is more idiomatic if not more correct
for (auto thisIter = allLoaded.begin(); thisIter != allLoaded.end(); /* moved the increment from here... */) {
    if ((*thisIter)->GetID() == this->mID) {
        thisIter = allLoaded.erase(thisIter);
    } else {
        /* ... to here */
        ++thisIter;
    }
}
Or just use a standard algorithm, and not write a loop in the first place.
 
allLoaded.erase(std::remove_if(allLoaded.begin(), allLoaded.end(), [this](AnimatedBitmap* other) {
    return other->GetID() == this->mID;
}));

 

 

Wait sorry, I'm still not following. So lets say in vector 1 2 3 4 5, I delete element 3 so now my iterator is pointing at element 4 right? I then check if it's hit the end and break. So it never reaches the end of the loop and never increments it again. I think your arrows were a little off so when you say "iterator points at this element" it just points at 1.  Isn't this how it should be 

before

1 2 3 4 5

      ^

after

1 2 4 5

      ^

 

If not then I'm not really understanding how the iterator works, because I thought that as you cycle it it points at the elements you're working on.

Share this post


Link to post
Share on other sites

Oh ok I think I see where I'm confused, I'm thinking of just a single element match for if like it is in my case, that is my id's are never reapeated so that if can't hit more than one thing at a time anyways. I see now. So in my case I should just break out as soon as I erase it, no need to even continue iterating. 

Share this post


Link to post
Share on other sites

I delete element 3 so now my iterator is pointing at element 4 right? I then check if it's hit the end and break.


But it HASN'T hit the end (necessarily). It's pointing at element 4. The last element is 5. erase doesn't make the iterator point at the last element, it makes it point at the element after the element that was erased.
 

So it never reaches the end of the loop and never increments it again. I think your arrows were a little off so when you say "iterator points at this element" it just points at 1.  Isn't this how it should be


Yes, I edited the post and it messed up the formatting. I'll edit it, but I'll also repost here.
 
// enter the loop, the iterator is pointing at 3
1 2 3 4 5 6
    ^

// erase the element; the iterator is now pointing at 4
// notice that every element after 3 has shuffled down, but the iterator has not moved
1 2 4 5 6
    ^

// increment the iterator - now it points at 5
1 2 4 5 6
      ^

// oops, skipped 4

So in my case I should just break out as soon as I erase it, no need to even continue iterating.


You could also do that. Edited by Oberon_Command

Share this post


Link to post
Share on other sites

Thank you, that question didn't make any sense. Basically I was getting an error "iterator not incrementable" and that's because I was erasing the last elemnt and then the loop was incrementing the iterator when it was already set to end(), so I thought that just checking for end would fix it and it did in my case, but for some reason I didn't think that the component doesn't have to be last. Basically just a stupid question. But thanks for your time.

Share this post


Link to post
Share on other sites

Just as an addition which might be notable in this context. If ordering is not an issue I think removing elements from a vector should be done iterating backwards over the range. E.g.

 

for (int64_t i = int64_t( v.size() ) - 1; i >= 0; --i )

{

   if ( should_delete( v[ i ] )

   {

       v[ i ] = v.back();

       v.pop_back();

   }

}

 

Note that I declared i as int. You need to be careful with the std::vector as you can 'overflow' if the vector is empty (the index type is declared unsigned). 

Share this post


Link to post
Share on other sites

Just as an addition which might be notable in this context. If ordering is not an issue I think removing elements from a vector should be done iterating backwards over the range. E.g.
 
for (int64_t i = int64_t( v.size() ) - 1; i >= 0; --i )
{
   if ( should_delete( v[ i ] )
   {
       v[ i ] = v.back();
       v.pop_back();
   }
}
 
Note that I declared i as int. You need to be careful with the std::vector as you can 'overflow' if the vector is empty (the index type is declared unsigned).


If you are going to iterate inreverse do it correctly.

for(auto i = v.size(); v--;) { ... }

Furthermore you should probably swap and pop not copy and pop

Share this post


Link to post
Share on other sites
Yup, I like this better if the size type is unsigned. My containers use a signed size type in which case I prefer my form. Personal preference.

I think to be formally totally correct we should move and pop.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement