Jump to content
  • Advertisement
Sign in to follow this  
xyuri

Iterating a vector while deleting certain elements?

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

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!