Sign in to follow this  

vector ... delete ... memory woes of C++ help!

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

Ok. Lets say I have a class Bots. Now I have vector<Bots*> bots; now lets say I have the following code:
for(vector<Bot*>::iterator i = bots.begin(); i != bots.end(); i++)
	if((*i)->getHealth() <= 0) // Kill the bot
	{
		delete (*i);    // ERROR
		bots.erase(i);
	}

Am I suppose to delete an element of vector, before erasing it, since it is a pointer?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sagar_Indurkhya
Ok. Lets say I have a class Bots.

Now I have vector<Bots*> bots;

now lets say I have the following code:
*** Source Snippet Removed ***

Am I suppose to delete an element of vector, before erasing it, since it is a pointer?


...and after you erase the iterator it is no longer valid. Which makes your loop break. Not to mention you didn't to tell us what error you were getting.

Share this post


Link to post
Share on other sites
As Washu said, when you erase the iterator it becomes invalid, so trying to increment to the next iterator will have undefined results. That is, on your first run through the loop everything seems to work fine. On the second run through your iterator is invalid, you increment it and it ends up pointing to random garbage, then when you try and dereference this everything dies. The loop you really want is something this:


for(vector<Bot*>::iterator i = bots.begin(); i != bots.end(); i++)
if((*i)->getHealth() <= 0) // Kill the bot
{
// Save an iterator to the previous element
vector<Bot*>::iterator prev = i-1;

delete (*i);
bots.erase(i);

// Since the current element is erased, what was the
// previous element is now the current element
i = prev;
}


Share this post


Link to post
Share on other sites
Quote:
Original post by joanusdmentia
As Washu said, when you erase the iterator it becomes invalid, so trying to increment to the next iterator will have undefined results. That is, on your first run through the loop everything seems to work fine. On the second run through your iterator is invalid, you increment it and it ends up pointing to random garbage, then when you try and dereference this everything dies. The loop you really want is something this:

*** Source Snippet Removed ***


Bit simpler:

std::vector<Bot*>::iterator i = bots.begin();
while(i != bots.end()) {
if((*i)->getHealth() <= 0) {
delete *i;
i = bots.erase();
continue;
}
++i;
}

Share this post


Link to post
Share on other sites
Edit note: I just noticed you've used "Bots", part of my post that I added later uses this class, the first part just refers to the class "Bot".

Note: if you have a ton of bots, this is going to be innefficient due to the fact that all the elements past i will be moved left one each time erase is called.

Here's an alternative that calls erase only once, on a range (which reduces the theoretical overhead from O(N*N) to O(N), meaning it should be faster for huge groups of bots)

Bot * delete_and_zero_if_dead( Bot * bot )
{
if ( bot->getHealth() <= 0 ) //is dead
{
delete bot;
return 0;
}
else //is alive
{
return bot;
}
}

void remove_dead_bots( void )
{
using namespace std;
transform( bots.begin() , bots.end() , bots.begin() , ptr_fun( & delete_and_zero_if_dead ) ); //not sure if the "ptr_fun" bit is necessary, but it can't hurt
vector< Bot * >::iterator new_end = remove_if( bots.begin() , bots.end() , bind2nd( equal_to< Bot * >() , 0 ) );
bots.erase( new_end , bots.end() );
}



Note that this code will preform worse than the original on a std::list, since for a list, erase( iterator ) is a constant time operation. This reduces the theoretical overhead to O(N), the same as this method. However, this method iterates over memory repeatedly, which is slow/bad for a list.

If one wanted to micro-optimize, one might merge the transform and remove_if steps into a single statement akin to:

remove_if( bots.begin() , bots.end() , delete_and_return_true_if_dead );

Or, more idiomatically, switch from "Bots *" to some sort of handle which would automatically delete the bot upon the handle's demise. E.g.:

vector< boost::shared_ptr< Bots > > bots;

//using a functor:
remove_if( bots.begin() , bots.end() , is_dead );

//using lots of std:: stuff:
remove_if( bots.begin() , bots.end() ,
compose1( //f(x) == g(h(x)) == ((x->getHealth()) <= 0)
bind2nd( less_equal< int >() , 0 ) , //g(x) == (x <= 0)
mem_fun( & Bots::getHealth ) //h(x) == (x->getHealth())
)
);



[Edited by - MaulingMonkey on May 15, 2005 7:43:11 PM]

Share this post


Link to post
Share on other sites
Thank you! I was kind of confused, because I was first introduced to iterators in java, where they have remove and insert built into iterator. I will take the more readable code, because this is for a large science project, and I prefer code to be readable than fast. Plus I will run it through the optimizing compiler.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sagar_Indurkhya
Thank you! I was kind of confused, because I was first introduced to iterators in java, where they have remove and insert built into iterator. I will take the more readable code, because this is for a large science project, and I prefer code to be readable than fast. Plus I will run it through the optimizing compiler.


Better to learn how to read that code than ignore it on the basis of readability, in my not so humble opinion :-).

Further, running it through an optimizing compiler will not reduce that O(N*N) example to O(N) - it's good for micro-optimization stuff, like inlining functions and unrolling loops - not so good for changing high level algorithms :-).

That said, it's not going to be a bottleneck point unless you're dealing with hundreds of bots, and not a major one unless you're dealing with thousands, most likely.

Share this post


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

remove_if( bots.begin() , bots.end() ,
compose1( //f(x) == g(h(x)) == ((x->getHealth()) <= 0)
bind2nd( less_equal< int >() , 0 ) , //g(x) == (x <= 0)
mem_fun( & Bots::getHealth ) //h(x) == (x->getHealth())
)
);


OMG, l33t! I didn't know about "compose1". Now I'm tempted to write a code generator for this kind of stuff, or something...

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
Original post by Sagar_Indurkhya
Thank you! I was kind of confused, because I was first introduced to iterators in java, where they have remove and insert built into iterator. I will take the more readable code, because this is for a large science project, and I prefer code to be readable than fast. Plus I will run it through the optimizing compiler.


Better to learn how to read that code than ignore it on the basis of readability, in my not so humble opinion :-).

Further, running it through an optimizing compiler will not reduce that O(N*N) example to O(N) - it's good for micro-optimization stuff, like inlining functions and unrolling loops - not so good for changing high level algorithms :-).

That said, it's not going to be a bottleneck point unless you're dealing with hundreds of bots, and not a major one unless you're dealing with thousands, most likely.


There will be about 500 bots... but this isn't in real time. The data is recorded to the harddrive, and then another program plays back the data and animates the bots on the screen.

Share this post


Link to post
Share on other sites
Just a hint!

There was an error in upper line:

for(vector<Bot*>::iterator i = bots.begin(); i != bots.end(); i++)

it is not i++ but ++i instead!

Begin != FIRST ELEMENT - that was the failure. You were trying to delete something you did not allocate. You could delete (*++bots.begin()).

Share this post


Link to post
Share on other sites
Quote:
Original post by Samurai Jack
for(vector<Bot*>::iterator i = bots.begin(); i != bots.end(); i++)

it is not i++ but ++i instead!

Since the expression "i++" is discarded it does not matter if you use "i++" or replace it with "++i". They both increment i by one.

Quote:

Begin != FIRST ELEMENT

I'm not exactly sure what you mean by that, but begin() does point the actual first element. Maybe you mixed it up with end() pointing to the (nonexistent) element after the last?

Share this post


Link to post
Share on other sites
Quote:
Original post by Samurai Jack
Just a hint!

There was an error in upper line:

for(vector<Bot*>::iterator i = bots.begin(); i != bots.end(); i++)

it is not i++ but ++i instead!

Begin != FIRST ELEMENT - that was the failure. You were trying to delete something you did not allocate. You could delete (*++bots.begin()).


What is it with people posting blatently false information these days?!?

std::vector< int > ints;
ints.push_back( 1 );

//same value:
assert( ints[0] == 1 );
assert( *(ints.begin()) == 1 );
assert( ints.front() == 1 );

//same addresses:
assert( &(ints[0]) == &(*ints.begin()) );
assert( &(ints[0]) == &(ints.front()) );


Further, the following two pieces of code are identical:

for ( int i = 0 ; i < 10 ; ++i )
for ( int i = 0 ; i < 10 ; i++ )

There is no difference in what I will be inside the loop.

for(vector<Bot*>::iterator i = bots.begin(); i != bots.end(); ++i)
{
delete *i;
}


Is the same as:

vector< Bot * >::iterator i = bots.begin();
while ( i != bots.end() )
{
delete *i;
++i; //same as i++
}


NOT:

vector< Bot * >::iterator i = bots.begin();
while ( i != bots.end() )
{
delete *(++i);
}


The only difference is that with some iterator types, post-incrementing can be inefficient - that is, ++i will be faster than i++.

Share this post


Link to post
Share on other sites

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