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.

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 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 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 on other sites
Isn't the iterator invalidated when adding/removing items?

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 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 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 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 itstd::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 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 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 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 on other sites
Quote:
 Original post by OluseyiSwap 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 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.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628682
• Total Posts
2984214

• 11
• 13
• 13
• 9
• 10