# std::vector wierdness (UPDATE: now about memory not freeing)

This topic is 3302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Okay, I have a simple set-up for a game: there's a player who has a weapon which in turn has a vector of projectiles. It's really pretty basic, take a look at the source (I commented it all very extensively so it should really be self-explanatory):
void CWeapon::Draw ( )
// draws a weapon
{
// draw weapon itself

// draw all its projectiles
std::vector<CProjectile*>::iterator i;
for ( i = Projectile.begin ( ); i < Projectile.end ( ); i++ )
// loop through all projectiles currently in the vector
{
// draw this projectile
(*i)->Draw ( );

if ( (*i)->Distance > 200.0f )
// if this projectile has gone too far
// erase it from vector
Projectile.erase ( i );
}
}

void CWeapon::Shoot ( void )
// shoots a weapon
{
// do a bunch of unrelated stuff (play a sound etc.)

// add a new projectile to this weapon's vector
Projectile.push_back ( new CProjectile ( ) );
}


Weapon.Projectile is the std::vector<CProjectile*>, Weapon.Draw ( ) is called every frame and Weapon.Shoot ( ) is called repeatedly when the left mouse button is held down. Now, all this works only for every second or third shot. It's really unpredictable. Sometimes three shots in a row work, sometimes three won't work, or two etc. It seems completely random. Shots that work are drawn, move away from the player and get erased once they've gone to far, shots that don't "work" are not drawn although they DO get added to the vector (I check std::vector.size ( ) via debug output) but then do not move and thus never get deleted either. I have no idea what's going wrong here. I cross-checked this code with the examples over at CodeGuru.com and it seems to be the correct way. On the other hand, I'm still somewhat new to std::vectors. Any ideas? Help/feedback is greatly appreciated. Thanks. [Edited by - d h k on January 31, 2009 9:09:54 AM]

##### Share on other sites
Erasing elements while you're iterating through a vector has to be done very carefully. Basically, when you erase(i), the i iterator is no longer valid, so bad things happen when the loop iterates it. You can use the return value of erase() to get the iterator to the element after the one you just erased. So your modified loop would look like:
	for ( i = Projectile.begin ( ); i < Projectile.end ( );)	{		// draw this projectile		(*i)->Draw ( );		if ( (*i)->Distance > 200.0f ) {			i = Projectile.erase ( i );                } else {                        ++i;                }	}

edit: also, your loop leaks memory. Consider adding a delete call, or use a smart pointer to handle deletion for you.

##### Share on other sites
The problem is that you are erasing elements from the vector *while* looping through it. Erasing an element from the vector invalidates the iterator you are using, check the documentation of the STL. What you might consider is to have each projectile have an is_valid flag, or something of the sort. Rather than erase it in the loop, you just mark it as invalid when the distance is too great (it no longer gets drawn or updated). Then, after you've iterated over all elements, you erase those (maybe using remove_if) which are no longer valid.

Cheers,
Rob

##### Share on other sites
You can use std::for_each to apply the drawing. Then use std::remove_if to swap all dead projectiles to the back of the vector where they can be efficiently erased in bulk.

Consider storing smart-pointers (boost::shared_ptr for example) rather than raw pointers to your projectiles; this is even more relevant since you've made the mistake of forgetting to delete the memory that you new.

##### Share on other sites

It looks as if SiCrane's way is the quickest to implement, so I decided to go with that for the moment (the other solutions seem more efficient/elegant, though, so I will replace the implementation later on, once I get it to work in the really simple way). My loop now looks like this:

std::vector<CProjectile*>::iterator i;for ( i = Projectile.begin ( ); i < Projectile.end ( ); ){	(*i)->Draw ( );	if ( (*i)->Distance > 200.0f )	{		delete *i;		i = Projectile.erase ( i );	}	else		++i;}

Now, only the first shot works and the rest are never added to the vector..?

Thanks again.

##### Share on other sites
Further investigation has shown that the problem with shots appearing sometimes and sometimes not has nothing to do with the erasing stuff. If I just let projectiles fly forever it still doesn't always create a new one when I shoot. Again, they ARE added to the vector (::size ( ) says so) but they are not drawn.

Any more ideas? I'm really not sure what's going on.

[Edited by - d h k on January 24, 2009 4:25:37 PM]

##### Share on other sites
Relevant code would include the initialization (are the bullets being generated where they should be? If not, they could be off the screen), and the rendering code.

##### Share on other sites
I'll try my best to present all relevant code.

// projectile definition, each weapon has a std::vector<CProjectile*>class	CProjectile{	public:		float		X, Y, Z;		float		Yaw, Pitch, Roll;		float		Distance;		CVector3	ForwardAxis;		CProjectile ( CVector3 forward_axis, float yaw, float pitch, float roll )		// constructor		{			ForwardAxis = forward_axis;			Yaw = yaw;			Pitch = pitch;			Roll = roll;		}		void		Draw ( CModel *shot_model );};// called every frame by a weapon in order to draw the vectorstd::vector<CProjectile*>::iterator i;for ( i = Projectile.begin ( ); i < Projectile.end ( ); i++ )	(*i)->Draw ( &ProjectileModel );// in the line above, ProjectileModel is a pointer stored as a member in CWeapon which is// loaded on init and represents the projectile// when player shootsProjectile.push_back ( new CProjectile ( player.ForwardAxis, player.Ship.Model.Yaw, player.Ship.Model.Pitch, player.Ship.Model.Roll ) );

And this is what CProjectile::Draw ( ) does...

void CProjectile::Draw ( CModel *shot_model ){	shot_model->Position.X = ForwardAxis.X * Distance;	shot_model->Position.Y = ForwardAxis.Y * Distance;	shot_model->Position.Z = ForwardAxis.Z * Distance;	shot_model->Yaw = Yaw;	shot_model->Roll = Roll;	shot_model->Pitch = Pitch;	shot_model->Draw ( );	Distance += 7.0f;}

The draw function gets passed a pointer to a model, positions the model accordingly, draws it and then increases the distance. I know the model stuff is working fine because it works for players/enemies/objects etc. I personally don't see any reason why it would NOT draw/handle every 3rd or sometimes 4th shot...

I'm really clueless and extremely thankful for any food for thought etc.

##### Share on other sites
You never seem to initialize Distance. Try throwing Distance = 0.0f; into CProjectile's constructor. You'd be able to confirm this by using a debugger to put a breakpoint on the call to shot_model->Draw();, and taking a look at the variable values.

You also seem to never use X/Y/Z of CProjectile -- I'd remove them if this is the case. Otherwise, I'd initialize them as well -- uninitialized variables tend to lead to random-ish behavior like you're experiencing now.

What's probably happening, for the bullets to show up at all in the first place, is that std::vector's allocation buffer is initialized to zero at first. (You should not rely on this behavior as it is not required by the standard!) However, when you erase items, then add new ones, the memory isn't rezeroed -- so any uninitialized variables (e.g. Distance) actually get given the value of an old bullet (e.g. one with Distance > 200.0f).

##### Share on other sites
Wow, you were absolutely right! What a stupid mistake, too... :)

X, Y, Z were a relict from an older version, I removed them. Putting a "Distance = 0.0f;" into the Projectile constructor did the trick!

Thanks a ton!

##### Share on other sites
No problem. relict (or "dead") code is fairly common phenomena -- by removing it you help improve the readability of the code. In this case, we no longer have to worry about those members not being initialized, because they no longer even exist :).

Eyeballing constructors to make sure everything is initialized can be a good habit to form -- stupid mistake or not, it's one we all make, repeatedly :).

##### Share on other sites
UPDATE

I'm warming this thread up because I have a related issue at the moment, hope that's okay.

I have installed the boost libraries now and switched to using std::vectors with boost::shared_ptrs.

This is not about projectiles anymore, it's about enemies. There is a global std::vector of boost smart pointers to CEnemy in my project. Put in code:

// in enemy.hclass CEnemy{	// bunch of unrelated elements};typedef boost::shared_ptr<CEnemy> CEnemyPtr;// in enemy.cpp, top of the file (global scope)std::vector<CEnemyPtr> enemies;// in enemy.cpp when a new enemy is createdenemies.push_back ( CEnemyPtr ( new CEnemy ( ) ) );// in enemy.cpp when an enemy is killed and removedstd::vector<CEnemyPtr>::iterator i;for ( i = enemies.begin ( ); i < enemies.end ( ); ){	if ( (*i)->Health <= 0 )	{		// TODO: free memory		i = enemies.erase ( i );				}	// loop continues, unrelated

It compiles and works just fine but when I kill an enemy in the game, it doesn't free the memory. I use the Task Manager in Windows XP to monitor memory usage and these are the detailed results:

The game loads up initially and memory is allocated for all the enemies. Then, I kill an enemy but memory usage stays the same. As soon as I kill all enemies, I create a bunch more and more memory is allocated. It's never free'd.

I do a debug check on enemies.size ( ) and it's correct, so the line "i = enemies.erase ( i );" is being called and working, it removes the element i from the std::vector correctly.

I thought boost smart pointers would free memory automatically. Then why doesn't that happen in my project? I'm somewhat new to the boost library (installed it yesterday for the first time) so it might be an easy fix, just can't find any info on it on the net anyways.

Any help is greatly appreciated!

##### Share on other sites
Does your CEnemy correctly clean up all its members in its destructor? If CEnemy is part of an inheritance hierarchy does it have a virtual destructor? If not, can't they be stored by value in the vector?

The task manager isn't a great way to monitor memory, instead see if you can use a memory leak tracker.

##### Share on other sites
Well, there isn't very much to destroy, I believe. Take a look:

class CEnemy{	public:				CShip			Ship;		CVector3		ForwardAxis;		float			Thrust;		float			DesiredThrust;		int			Health;		CSprite			Explosion;		CSound			ExplosionSound;		CGroup			*Group;		CEnemyType		Type;		CEnemy ( CEnemyType type, CGroup *group, float x, float y, float angle )		{			Type = type;			Load ( group );			Targetted = false;			Ship.Model.Position.X = x;			Ship.Model.Position.Y = y;			Ship.Model.Position.Z = 0.0f;			Ship.Model.Roll = 0.0f;			Ship.Model.Pitch = 0.0f;			Ship.Model.Yaw = angle;			Thrust = 0.0f;			DesiredThrust = 0.0f;		}		~CEnemy ( )		{			delete Group;		}		void Load ( CGroup *group );		void Draw ( void );		void UpdatePosition ( void );};

I only have one standard pointer in the class and I do delete it. What else am I supposed to get rid of?

Thanks for the quick response!

##### Share on other sites
First: What's a cenemy? (What are you hoping to accomplish by putting a 'C' in front of the class name? Whoever told you to do this was, with 99.9% confidence, completely misguided.)

These things bother me enough that I've taken the liberty of deleting the offending 'C's from the rest of this post (including in quotations). :)

Quote:
 Original post by d h kThis is not about projectiles anymore, it's about enemies. There is a global std::vector of boost smart pointers to Enemy in my project. Put in code:*** Source Snippet Removed ***It compiles and works just fine but when I kill an enemy in the game, it doesn't free the memory.

Unless you're letting some other part of the code get another shared_ptr to the same Enemy, yes, it does.

Quote:
 I use the Task Manager in Windows XP

This is an incredibly inaccurate way to monitor memory usage. In fact, it's effectively worthless as a leak detection tool.

However, if you don't actually want to share the pointers (as mentioned above) - if you only want the pointers for the sake of polymorphism, then you should instead use something like boost::ptr_vector<Enemy>.

But do you actually need to store things by pointer? What are you worried will happen if you just use a std::vector<Enemy>? Are there actually classes derived from Enemy that implement virtual functions?

Quote:
 Original post by d h kWell, there isn't very much to destroy, I believe. Take a look:*** Source Snippet Removed ***I only have one standard pointer in the class and I do delete it. What else am I supposed to get rid of?Thanks for the quick response!

As a rule, any time you need to write a destructor, you need to write a copy constructor and assignment operator as well. Does the Enemy actually "own" its Group? Consider whether you should store a Group by value, or perhaps use boost::shared_ptr for this data member.

BTW, what does "Load"ing a Group do? (And why would you pass an "unloaded" group to the constructor instead of a loaded one?)

##### Share on other sites
I have reconsidered the pointers and you're right, it would do to just have them as value.

So, this works but the result in the Task Manager is just the same. What are some good tools to check for memory leaks etc.?

##### Share on other sites
Most leak detectors are platform and/or compiler specific. For example, MSVC comes with a built in leak detector in it's CRT implementation and on linux, there's valgrind.

##### Share on other sites
I recommend getting Process Explorer if you want a task manager-like application.
It has lots of lovely information, including 'Virtual Size', 'Working Set' and 'Private Bytes'. Doubleclick a process to get lots more info.

##### Share on other sites
UPDATE (again)

Okay, I'm using Process Explorer now and this is the private bytes result when running the game:

This is exactly what the Task Manager showed. You can clearly see how memory is allocated for the enemies but not ever free (each increasing slope in the graph represents the time six new enemies are pushed back into the vector). Again, I start with six enemies, kill them one by one and when the last one has died, I create six new ones. All this works perfectly in the game and when I display the ::size ( ) of my std::vector holding my Enemy structure I see that that works as well (starts out with 6 of 6 enemies, decreases correctly, when it hits zero it jumps back to 6 etc).

I want to free the memory of an enemy after it died, but somehow that's not working.

The relevant code:

std::vector<CEnemy> enemies;// when creating a new enemyenemies.push_back ( CEnemy ( type, group, x, y, angle ) );// when getting rid of onestd::vector<CEnemy>::iterator i;for ( i = enemies.begin ( ); i < enemies.end ( ); ){	if ( (*i).Health <= 0 )	{		// TODO: free memory		i = enemies.erase ( i );	}		// loop continues, unrelated

For the record, I don't use the new operator ONCE in my whole project, so what memory could not get freed?

##### Share on other sites
It's normal, vector has never free memory. Method size() return number of elements in vector not size of it's storage. Look at method capacity()(Returns the maximum possible number of elements without reallocation) and resize to understand vector usage.

##### Share on other sites
Quote:
 Original post by ZahlmanFirst: What's a cenemy? (What are you hoping to accomplish by putting a 'C' in front of the class name? Whoever told you to do this was, with 99.9% confidence, completely misguided.)These things bother me enough that I've taken the liberty of deleting the offending 'C's from the rest of this post (including in quotations). :)

I agree (although I'm not offended to the same extent). Use namespaces to avoid naming clash (or to distinguish that it's code from a particular source), rather than the letter C.

-------------

With regards to the current question, you say you don't use new at all in the whole project, yet the first code snippet pasted made use of new (and was not freeing the memory when you called erase). Are you sure??? If you're allocating memory when pushing something into a vector, you will NEED to free that memory before removing it from the vector (since the pointer would most likely be lost after the call to erase).

##### Share on other sites
Try using std::list instead of std::vector. The only gotcha is that you won't be able to use operator < on list iterators like you can with vector iterators, but you can use operator != instead.

##### Share on other sites
Thanks for the tips, guys. However nothing solved the issue yet, I'm afraid.

_fastcall: I tried std::lists, they work, but there's no change.

dashurc: The code I posted in the original post is no longer up to date. The last posted lines are what I'm currently using. I'm not using the new operator there anymore because I changed from a vector of pointers to storage by value (ie. I changed from std::vector<CEnemy*> to std::vector<CEnemy>). I really don't use the new operator anymore. Nowhere.

Ocelot: I see what you say, but how would looking at the capacity of the vector solve anything? Can you elaborate?

Please keep it coming. This is really holding me up and I'm pretty stumped.

[Edited by - d h k on February 1, 2009 3:06:41 PM]

##### Share on other sites
Vectors allocate memory by a percentage of their original size. You can say that at any given point in time, a vector's capacity is equal to or greater than its size. This is done to save speed, such that sequential push_back() calls don't all allocate memory, only the first couple do, such that the consequential ones already have enough memory and need to only copy the data.

##### Share on other sites
What about counting the numbers of times a certain destructor is called? Say, make each class count the amount of times they're constructed and destructed and print that out every X seconds. Then, look to see which is rising continually.

Make sure you account for all resources this way - external libraries may also be your culprit, by misuse or by bug in their code.