Jump to content
  • Advertisement
Sign in to follow this  
Northernlight

[C++]Remove objects from vector

This topic is 3032 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); 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);
					_defenceEvents.erase(elementsToBeErased);
				}
			}
		}

Share this post


Link to post
Share on other sites
Advertisement
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, 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
Thank you very much for your suggestions guys. I think I have enough info to solvethis problem now. I will try to implement these solutions when I'm back at my compiler :)

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
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!