Sign in to follow this  

Iterating a vector while deleting certain elements?

This topic is 4688 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 have some code which has an iterator to step a vector, but I am deleting certain elements along the way, but when I get to deleting the last element the application crashes (I dont quite understand the logic as to why, but there is bound to be a readon) I am away from my dev pc but does anyone know of a way to iterate a vector while deleting elements? Thanks.

Share this post


Link to post
Share on other sites
Depending on the structure of your loop, you might be deleting an element and then attempting to read it. Whatever it is you're trying to do, I don't think it's a good idea to iterate through something dynamic. My suggestion is iterate through the original, but keep a copy where you can delete items from.

Share this post


Link to post
Share on other sites
Hi, you should not be looping through the vector and deleting certain elements along the way, think of a vector as a growable array, everytime you delete something, it shifts all the elements up. Your last item is no longer valid.
Try using a list instead if you're doing all this deleting or maybe do a simple mark the element as invalid or swap them to the end of the vector and keep the number of elements in the vector yourself.



-Ken

Share this post


Link to post
Share on other sites
Yes, because elements may be assigned to a new memory location for vectors so iterators are invalidated. List doesn't use contiguous memory, and has O(1) for deletion. So it looks like he's probably better off using a list.

Share this post


Link to post
Share on other sites
If you're only deleting the current element then the remove method should return a new valid iterator.
Oterwise you could keep track of the current index instead of an iterator and adjust it (decrease it by one) whenever deleting something before the current entry.

However frequently deleting entries in the middle of a vector is going to be slow. As tiburon stated you might want to use a linked list instead.

Another alterantive (if you're only deleting the current element) would be to keep track of both a source and destination pointer in the vector, and only copy the source onto the destination (and increase both indices) whenever you're not deleting.
There's also the famous "fill the hole with the last element" strategy, if you don't mind the vector getting out of order.

On my old project we actually developed a list that kept track of it's iterators just so they could be adjusted whenever an element had been deleted. In retrospect it might seem like overkill but it did solve some real problems and it's an interesting example of where STL just isn't enough.

Share this post


Link to post
Share on other sites
Thank you all for your input :-) it is much appreciated.

I might give the linked list a try (I think they talk about it in the C++ book I have)

Share this post


Link to post
Share on other sites
Your original question was not really answered. If you want to delete items from a vector or list while iterating (without crashing :), do this:



std::list<int> myList; // let's assume this list has stuff in it
std::list<int>::iterator i;

for (i = myList.begin(); i != myList.end(); /* NOTE: no ++i here! */)
{
if (*i < 5) // or whatever
{
// remove this item
i = myList.erase(i);
}
else
{
++i;
}
}



Share this post


Link to post
Share on other sites
WooHoo ! Thanks mother, your method works like a charm :-)

Now that I'm near my beloved code, I can share the working version of what was giving me trouble before:

	/*
* Draw the bullets on the screen
*/
std::vector<BULLET>::iterator BulletI;
for (BulletI = bullets.begin(); BulletI != bullets.end();)
{
//UPDATE (Assume they are all player bullets for now!)
BulletI->y += (BulletI->bulletInfo.speed * timeframe);
BulletI->ttl -= timeframe;
if (BulletI->ttl <= 0)
{
//ERASE!
bullets.erase(BulletI);
}
else
{
//DRAW
glBegin(GL_LINES);
glColor3f(0.0f, 1.0f, 0.0f);
glVertex3f(BulletI->x, BulletI->y - 0.2f, 0.0f);
glVertex3f(BulletI->x, BulletI->y + 0.2f, 0.0f);
glEnd();
++BulletI;
}
}

Thank you all for helping out :-) It is much appreciated.

Share this post


Link to post
Share on other sites
No, you still are not erasing elements correctly. The iterator (BulletI) gets invalidated when you call erase. You can't go on and use it afterwards. Fortunately, the vector<>::erase function returns a valid iterator to the element after the one you just erased.

Simple change, though:

change:
bullets.erase(BulletI);

to:
BulletI = bullets.erase(BulletI);

Share this post


Link to post
Share on other sites
Quote:
Original post by Oluseyi
Swap all you to-be-deleted elements (continuous swapping with neighbors if order is important; swap with --end otherwise) to the end of the vector, then remove them.



This doesn't really work, because std::remove does not actually remove any elements from a container (it can't). Calling std::remove is good, though, and it will return an iterator to the 'new end' of the container. You can then use that to call erase() on whatever container you are using, and erase the elements between the iterator returned, and .end(). Swapping is unnecessary - you are trying to trash certain elements, no need to swap to preserve; what std::remove will do is move all the elements you don't want removed to the front of the container, allowing you to call erase to remove the last elements (which are NOT the elements you removed swapped to the end, even though some people seem to think they might/should be)

If you want to divide the container, try looking at std::partition or the like.

Best regards.

Share this post


Link to post
Share on other sites

This topic is 4688 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.

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