Sign in to follow this  
VanillaSnake21

Proper way to erase an element from a vector when iterating

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

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

Or just not delete during iteration. You can push indices or iterator values in another vector, then just reverse iterate that and erase or otherwise remove from the primary vector as you go.


You could store iterators to erase separately, but depending on how your memory allocation is set up and how big your vectors are, the performance cost of a heap allocation for the second vector might be more than just erasing as you go. Once you know the proper way to do it, erasing as you go requires less code, less memory, and sometimes less time.

Or, again, you could just use the standard algorithms (which are probably less costly than doing it yourself - std::remove and std::remove_if move the elements around in a "smarter" way than straight iteration + erase) and only micro-optimize if your profiler tells you that removing things from vectors is a problem. Edited by Oberon_Command

Share this post


Link to post
Share on other sites

Any way I can ask for a follow up? I'm hitting a weird memory breakpoint on vector erase, it doesn't give me a call stack for some reason. I've only seen that happen before if there is some corruption going on, which I hope this isn't the case. This is the context:

POINT corner = FindNearestSnapPoint({ int(xPos + 0.5f), int(yPos + 0.5f) });
				//make sure that there is no other bitmap in that cell, if so delete it
				auto vIter = LandSpriteList.begin();
				for (vIter; vIter < LandSpriteList.end(); vIter++)
				{
					if (corner.x == vIter->GetPosition().x && corner.y == vIter->GetPosition().y)
					{
						LandSpriteList.erase(vIter);
						break;
					}
				}

Just seeing if there is an image in the place where mouse is clicked already and erasing it from the list if so.

But what happens is that when the vector tries to move all the elements above the one deleted down, it breaks inside memcpy.

I'm not looking for an answer as to why as that probably involves looking over a bunch of other code, but it would help to know what is the exact sequence of events once erase is called?

 

LandSpriteList contains AnimatedBitmap, I set a break point in AnimatedBitmap destructor and for some reason it's not even called when the error happens, it just goes straight to memcpy, which is weird to me since I'd expect memcpy be called AFTER the element was already deleted or is something else happening here? 

 

Also I'm not sure if this is part of normal behaviour, but since I set the breakpoint inside the destructor, I've noticed it. If I insert an element as such

AnimatedBitmap ins = *currentInsertElement;
				ins.SetPosition( corner.x, corner.y);
				LandSpriteList.push_back(ins);

It calls the destructor at the end, so far so good, we're destroying the "ins" temporary variable. Now I insert a second bitmap, again I hit the destructor at this point, but now twice, once for the first image once for the new one. And this happens as many times as there are bitmaps, so on the 4th insertion, the destructor is called 4 times. Is that something up with my code or am normal behaviour? 

 

 

This is my destructor if it helps any:

AnimatedBitmap::~AnimatedBitmap()
{
	if (allLoaded.size())
	{
		vector<AnimatedBitmap*>::iterator thisIter;
		for (thisIter = allLoaded.begin(); thisIter < allLoaded.end(); thisIter++)
		{
			if ((*thisIter)->GetID() == this->mID)
			{
				thisIter = allLoaded.erase(thisIter);
				break;
			}
		
				
		}
	}
	vector<BITMAP_FILE>::iterator vIter;
	for (vIter = frames.begin(); vIter < frames.end(); vIter++)
	{
		Unload_Bitmap_File(&(*vIter));
	}
}

Share this post


Link to post
Share on other sites

 

Or just not delete during iteration. You can push indices or iterator values in another vector, then just reverse iterate that and erase or otherwise remove from the primary vector as you go.


You could store iterators to erase separately, but depending on how your memory allocation is set up and how big your vectors are, the performance cost of a heap allocation for the second vector might be more than just erasing as you go. Once you know the proper way to do it, erasing as you go requires less code, less memory, and sometimes less time.

Or, again, you could just use the standard algorithms (which are probably less costly than doing it yourself - std::remove and std::remove_if move the elements around in a "smarter" way than straight iteration + erase) and only micro-optimize if your profiler tells you that removing things from vectors is a problem.

 

 
I'm far more concerned about gibberish code and swarms of bugs than performance.
 
std::remove_if is the best option if you don't mind that it's iterating the whole thing within itself. I assumed (perhaps incorrectly) that OP was talking about deleting things while doing other work on the vector elements. If you're already doing a pass then you may as well mark and sweep. I'm not sure why you're concerned about 'more code' here a vector push instead of deletion gymnastics will make your pass far easier to read. If performance really is an issue then just set the reserve to something reasonable on the auxiliary vector. I can't imagine it being a significant issue unless you're in a constrained environment.
 
 

tl;dq


First code segment:

#include <algorithm>

auto rmv_iter = std::remove_if(LandSpriteList.begin(), LandSpriteList.end(), [corner&](whatever_is_in_this_vector& thing) { return corner.x == thing.GetPosition().x && corner.y == thing.GetPosition().y; });
std::erase(rmv_iter, LandSpriteList.end());

Second code segment:

LandSpriteList.emplace_back(*currentInsertElement);
LandSpriteList.back().SetPosition(corner.x, corner.y);

Third code segment:

#include <algorithm>

AnimatedBitmap::~AnimatedBitmap() {
  std::erase(std::remove(allLoaded.begin(), allLoaded.end(), this), allLoaded.end());

  //give the frames RAII and shove them in a vector and you won't have to fret about this
  for(auto& frame : frames) { Unload_Bitmap_File(&frame); }
}

I have no idea where your problems are coming from because I can't see the larger context of your code. If you can get on the chat you can probably get better help with this in real time.

Share this post


Link to post
Share on other sites

std::remove_if is the best option if you don't mind that it's iterating the whole thing within itself. I assumed (perhaps incorrectly) that OP was talking about deleting things while doing other work on the vector elements.


You can technically do work in a remove_if predicate - just have the argument take a non-const object. I wouldn't recommend that, though, unless you know how your standard library's implementation works. I don't know if the standard guarantees that remove_if will only run the predicate each element once. In my own code, when I need to update AND release, I have an algorithm that does what remove_if does under the hood that has a different name - consume_if - to distinguish it from remove_if.
 

If performance really is an issue then just set the reserve to something reasonable on the auxiliary vector.


I'm talking about the performance hit incurred by the heap allocation itself. It's probably fine if you're only doing it once a frame, but if you're doing this a lot of times a frame, that's probably bad. Edited by Oberon_Command

Share this post


Link to post
Share on other sites

I'm talking about the performance hit incurred by the heap allocation itself. It's probably fine if you're only doing it once a frame, but if you're doing this a lot of times a frame, that's probably bad.

 

I was thinking more along the lines of doing it once, maybe twice, per thread.

 

--------

 

VanillaSnake came to the chat and we resolved OP. The issue was that AnimatedBitmap created some external references to itself (in 'allLoaded'). LandSpriteList is a vector of AnimatedBitmap and when it would reallocate or shuffle the vector the external refs would become invalidated, but were later being dereferenced, causing access errors.

Share this post


Link to post
Share on other sites

If we are talking about vector container and multiple erasings on single iteration...

Best way do not erase on itaration, becouse it will be data copy nightmare.

You can instead of erasing element copy to its place next element and on end iteration resize vector;

This will guaraty that one element wount be copied more than one time + resize copy.

Edited by serumas

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this