Public Group

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

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

1. 1
2. 2
JoeJ
20
3. 3
4. 4
frob
12
5. 5

• 10
• 13
• 21
• 13
• 20
• ### Forum Statistics

• Total Topics
632195
• Total Posts
3004704

×