Sign in to follow this  

[C++]Remove objects from vector

This topic is 2816 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

Hi, I find myself constantly struggling with problems related to deleting pointer objects stored in a std::vector. I have an eventmanager which is supposed to handle all the events in the game. The manager updates all events each cycle and cleans up after an event is finished. All events are pointer which must be deleted in addition to being removed from the vector to avoid memory leaks. The following code snippet is a typical update function on one of the event types. As you can see I try to mark the events which has finished and then delete them and remove them from the vector in the end. Through debugging I have found that the first element is deleted like intended but then strange things happen to elementsToBeErased vector. (Among other things it suddenly holds two identical iterators). When crashing at runtime it says the iterator is not dereferenceble in the line: delete (*elementsToBeErased[i]); Can anyone see what I'm doing wrong or recommend a better technique for doing this?
if(!_defenceEvents.empty())
		{
			std::vector<Event_Defence*>::iterator itr = _defenceEvents.begin();
			std::vector<std::vector<Event_Defence*>::iterator> elementsToBeErased;

			for(; itr < _defenceEvents.end(); itr++)
			{
					if((*itr)->eventFinished)//If an event has finished we delete the pointer and mark it for erasing
				{
					elementsToBeErased.push_back(itr);
				}else{
					(*itr)->update(deltaTime);//The actual update of the event
					if((*itr)->ableToMoveOn())
					canMoveOn = true;
				}
			}
			if(!elementsToBeErased.empty())//Erase the "empty" elements of the vector
			{
				const size_t vectorsize = elementsToBeErased.size();
				for(size_t i = 0; i < vectorsize; i++)
				{
					delete (*elementsToBeErased[i]);
					_defenceEvents.erase(elementsToBeErased[i]);
				}
			}
		}

Share this post


Link to post
Share on other sites
When you are erasing element from vector, you effectively reducing elementsToBeErased.size(), while your vectorsize is constant size of original vector. When you try to access 5th element vector of size 4, it gives you access error or invalid/NULL value for that index.

Additionally, when calling 'delete' on vector index, you are destroying and putting random value into it, if it is not NULL. Thus, when you are trying to erase elementsToBeErased[i], it wouldn't know which one it is, because it simply does not exist in vector.

What you should consider doing is a simple while loop, checking for size of elementsToBeErased to be equal to 0, popping values inside it and deleting straightaway.

Share this post


Link to post
Share on other sites
Thanks for your reply. Im afraid I don't quite understand what you are suggesting.

I just don't understand what you mean by "popping values inside" and delete straight away. The whole point of this is to erase a specific element from the _defenceEvents vector so I assume its ok to call this in the while loop:


_defenceEvents.erase(*elementsToBeErased.begin());



and in the end I suppose I must erase the first element of elementsToBeErased:


elementsToBeErased.erase(elementsToBeErased.begin());



How do I delete the actual pointer which is stored in _defenceEvents? And how do I pop in a new value afterwards so that the elementsToBeErased element can be erased?

Share this post


Link to post
Share on other sites
Erasing an element from a vector invalidates all iterators in that vector (Actually it might be all iterators referencing objects >= the erased object), so as soon as you erase one object, the iterators to all the other objects are invalid.

What Daniel is suggesting is:

// Don't use < for iterators, use != (< may not be available or may take a long time to evaluate)
for(std::vector<Event_Defence*>::iterator itr = _defenceEvents.begin(); itr != _defenceEvents.end();)
{
Event_Defence* object = *itr;
if(object->eventFinished)
{
delete object;
itr = _defenceEvents.erase(itr);
}
else
{
object->update(deltaTime);
if(object->ableToMoveOn())
canMoveOn = true;

// Next object
++itr; // Use pre-increment where possible
}
}

That's the "standard" way to iterate over a container, erasing objects as you go.

Share this post


Link to post
Share on other sites
Eww, why not just do this?

_defenceEvents.erase(remove_if(_defenceEvents.begin(), _defenceEvents.end(), [deltaTime](Event_Defence* event) -> bool
{
if(event->isFinished)
{
delete event;
return true;
}
event->update(deltaTime);
return false;
}), _defenceEvents.end());


[Edited by - pablo24 on March 31, 2010 5:32:38 AM]

Share this post


Link to post
Share on other sites
And in case NorthernLight does not use a C++0x compiler:

#include <algorithm>

bool finishedDeleter(Event_Defence* p)
{
if (p->isFinished())
{
delete p;
return true;
}
return false;
};

_defenceEvents.erase
(
std::remove_if
(
_defenceEvents.begin(),
_defenceEvents.end(),
finishedDeleter
),
_defenceEvents.end()
);

Things would be a lot easier with std::vector<shared_ptr<Event_Defence> > or boost::ptr_vector<Event_Defence>...

[Edited by - DevFred on March 31, 2010 6:41:30 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred

void finishedDeleter(Event_Defence* p)

Needs bool, and you should try not to use std:: when you don't need it because of ADL so that you can write optimized versions of the std functions for your own types and it will use those instead.

Share this post


Link to post
Share on other sites
Quote:
Original post by pablo24
you can write optimized versions of the std functions for your own types

Why would I ever want to do this? Can you give an example where the std functions aren't good enough?

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Why would I ever want to do this? Can you give an example where the std functions aren't good enough?


For example if you have structs that contain only POD data types, std::copy will default to a simple for loop copying element by element, when it would be preferable to just use memcpy or a similar optimized algorithm instead.

In that simple case though, you can just make the STL use the optimized version by defining the scalar type traits for your own type:

namespace std
{
template<class _Ty>
struct is_scalar<MyType> : true_type
{
};
}

Share this post


Link to post
Share on other sites
Quote:
Original post by pablo24
For example if you have structs that contain only POD data types, std::copy will default to a simple for loop copying element by element, when it would be preferable to just use memcpy or a similar optimized algorithm instead.

Can you name a major production compiler available today for a desktop development environment that does not automatically perform that optimization?

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Quote:
Original post by pablo24
For example if you have structs that contain only POD data types, std::copy will default to a simple for loop copying element by element, when it would be preferable to just use memcpy or a similar optimized algorithm instead.

Can you name a major production compiler available today for a desktop development environment that does not automatically perform that optimization?


It's just an example. When you have more complex types, the compiler might not do all the optimizations for you.

Share this post


Link to post
Share on other sites
Hi again. Just popped in to say that I implemented Evil Steves suggestion and it is working like a charm. Finally I have some sort of template to use when encountering problems with pointers in vectors again :)

Thanks a lot guys!

Share this post


Link to post
Share on other sites
I would probably arrange it like so:


struct Event_Defence_Processor {
double deltaTime;

bool operator()(Event_Defence*& event) {
if (event->eventFinished) {
delete event;
event = NULL;
return false;
}
event->update(deltaTime);
return event->ableToMoveOn();
}

Event_Defence_Processor(double deltaTime): deltaTime(deltaTime) {}
};

std::vector<Event_Defence*>::iterator begin = _defenceEvents.begin(), end = _defenceEvents.end();

canMoveOn = std::count_if(begin, end, Event_Defence_Processor(deltaTime)) != 0;
_defenceEvents.erase(std::remove(begin, end, NULL), end);



By the way, even when you do manually iterate over a container, there is no point in checking whether the container is empty first. When the container is empty, the .begin() will equal the .end(), and the loop will correctly execute zero times without causing any problems. "Special cases aren't special enough". :)

Share this post


Link to post
Share on other sites

This topic is 2816 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