Back to General and Gameplay Programming

Proper way to erase an element from a vector when iterating

General and Gameplay Programming Programming

Started by VanillaSnake21 November 23, 2016 03:10 AM

16 comments, last by serumas 7 years, 3 months ago

VanillaSnake21

211

Author

November 23, 2016 03:10 AM

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.

You didn't come into this world. You came out of it, like a wave from the ocean. You are not a stranger here. -Alan Watts

Oberon_Command

6,371

November 23, 2016 03:15 AM

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;
}));

VanillaSnake21

211

Author

November 23, 2016 03:53 AM

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.

You didn't come into this world. You came out of it, like a wave from the ocean. You are not a stranger here. -Alan Watts

VanillaSnake21

211

Author

November 23, 2016 04:00 AM

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.

You didn't come into this world. You came out of it, like a wave from the ocean. You are not a stranger here. -Alan Watts

Oberon_Command

6,371

November 23, 2016 04:03 AM

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.

VanillaSnake21

211

Author

November 23, 2016 05:06 AM

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.

You didn't come into this world. You came out of it, like a wave from the ocean. You are not a stranger here. -Alan Watts

frob

46,221

November 23, 2016 05:17 AM

The critical detail is the return value of vector::erase().

The command invalidates existing iterators from that point onward, including .end(). Since the iterator used in deletion becomes invalid, vector::erase() returns a new, valid iterator which addresses the item after the one that was removed, which potentially is the new .end() value.

When you call vector::erase() you need to capture the return value with the iterator you used in controlling the loop. This ensures your iterator continues to be valid. You need to test against .end() before incrementing since the newly-returned iterator might be at the end of the container after the value was removed.

When you are erasing from a container like that usually it is better to use a while loop rather than a for loop:


while( iter != container.end() ) {
  ...
  if( should_erase ) {
    iter = container.erase(iter);  // both erases the item and advances the iterator
  }
  else {
    ++iter; // advance the iterator
  }
}

Dirk Gregorius

2,918

November 23, 2016 05:02 PM

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

l0calh05t

1,829

November 24, 2016 06:10 AM

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

Dirk Gregorius

2,918

November 24, 2016 06:41 AM

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.

Proper way to erase an element from a vector when iterating

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Proper way to erase an element from a vector when iterating

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines