Sign in to follow this  
ChaosPhoenix

[Solved]STD Vector and Dynamic Memory Clean up

Recommended Posts

One thing after another tonight... I'm doing an exercise with Dijkstra and A*, so I have an STD vector of path nodes. I'm trying to clean up memory since I create a new path node as I explore the terrain. At then end of the program I basically have a vector that is filled with small ~ 16byte nodes that need to be deleted. My current loop to clean up the memory is this:
	tNode* deleteTemp = NULL;

	while(!m_Closed.empty())
	{
		deleteTemp = m_Closed.back();
		m_Closed.pop_back();
		delete deleteTemp;
	}


This works great till I get to the last item in the vector, then it causes a _BLOCK_TYPE_IS_VALID debug assertion and crashes(only in Debug of course). While I can just shrug this off, since it works in release mode, I'd rather just try and fix the problem. What is a good way to delete dynamic memory that is contained within an STD vector? Is my way alright? Is there a better method? Is this even the reason for the crash(the debugger says it is)? [Edited by - ChaosPhoenix on November 7, 2006 8:08:41 AM]

Share this post


Link to post
Share on other sites
Your way should work, I think... Give this a whirl though and see if it still crashes:


//assuming m_Closed declared as follows
//std::vector<tNode*> m_Closed;

std::vector<tNode*>::iterator ite = m_Closed.end();
for( std::vector<tNode*>::iterator it = m_Closed.begin(); it != ite; ++it )
{
delete *it;
}
m_Closed.clear();





Definitely do _NOT_ ignore memory crashes in debug. Just because it doesn't crash in Release doesn't mean there's no bug; in Release you have a silent bug. It's not crashing but it's likely over-writing or leaking memory; both of which are amongst the hardest to find and most deadly of bugs; second only to thread bugs.

-me

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Or even easier, don't make the vector of tNode not tNode*. No need to make it a pointer, unless you NEED a pointer, don't use one. You can always get the pointer if you need it later, there is no valid reason why you need tNode*.

This way you don't have any memory leaks.

Share this post


Link to post
Share on other sites
Still crashing and I don't understand why. I actually tried a method like the one you suggested earlier.

The node it keeps blow up on is declared as:


// Create our root node.
tNode* root = new tNode;

root->pParent = NULL; // No parent
root->x = pMap->GetStartingPointX(); // Origin X
root->y = pMap->GetStartingPointY(); // Origin Y
root->tCost = 0; // No cost



It's then placed in an "Open" list, starts the path finding loop, and is instantly removed and placed into the closed list where it sits till the end of the program. I don't *think* that node is the problem, I find it odd that all elements of the vector can be deleted fine, except for the final node.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Or even easier, don't make the vector of tNode not tNode*. No need to make it a pointer, unless you NEED a pointer, don't use one. You can always get the pointer if you need it later, there is no valid reason why you need tNode*.

This way you don't have any memory leaks.


The path finding solution uses a list of tNodes to traverse and find the path, so having them dynamically declared makes life much easier (except for the clean up, ofcourse).

Share this post


Link to post
Share on other sites
Quote:
Original post by ChaosPhoenix
the program. I don't *think* that node is the problem, I find it odd that all elements of the vector can be deleted fine, except for the final node.


Maybe you already deleted root somewhere in your program?

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Or even easier, don't make the vector of tNode not tNode*. No need to make it a pointer, unless you NEED a pointer, don't use one. You can always get the pointer if you need it later, there is no valid reason why you need tNode*.

This way you don't have any memory leaks.


It looks like his tNodes have a pointer to a parent tNode (which is presumably in the same list)... so that pretty much requires using a pointers to dynamically allocated memory.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
He could redesign his tNode to be more efficent also. tNode.mParent (please don't use hungarian notation like p for pointers..) can point to a spot in the vector instead of a pointer.

It would be easier for the OP to slightly redesign his class to be safer instead of working around an issue.

In all honesty, pointers should be a last resort, when there is no way around using one. It eliminates mistakes. This is why languages like C# really don't use them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
He could redesign his tNode to be more efficent also. tNode.mParent (please don't use hungarian notation like p for pointers..) can point to a spot in the vector instead of a pointer.


IMO, that would be a terrible design. It means a node can really only exist in the context of a vector. It can only have a parent if its parent is in a vector. If anything was added to the vector, the index (or iterator) would now point to something different. Basically, you could never more anything around, w/o having to scan every node and update its parent. Almost certainly, this would lead to more mistakes, and more difficult coding, than simply using pointers.
That design would only make sense in a very limited context.

Using pointers isn't hard - learn to use them - they are the proper way to go for a case like this. It sounds like you understand what to do anyway - the problem is mostly somewhere else in your program.

If you need to, consider using one of the smart pointers in the boost library that works when used in containers (shared_ptr I think?).

If not, then here is some convenient code:

struct delete_object
{
template <typename T>
void operator()(T *ptr){ delete ptr;}
};


then you can just do


std::for_each( m_Closed.begin(), m_Closed.end(), delete_object());



[Edited by - phil_t on November 6, 2006 9:40:27 PM]

Share this post


Link to post
Share on other sites
Also, ChaosPhoenix, do you understand who "owns" the pointers to the tNode objects? e.g. if the vector "owns" them, then you should call delete on each item in the vector as you are doing - in that case though, you need to make sure your tNode destructor doesn't call delete on the pParent member!

Although I have never used it, shared_ptr would probably eliminate this responsibility.
http://www.boost.org/libs/smart_ptr/shared_ptr.htm

Share this post


Link to post
Share on other sites
Quote:
Original post by phil_t
Quote:
Original post by ChaosPhoenix
the program. I don't *think* that node is the problem, I find it odd that all elements of the vector can be deleted fine, except for the final node.


Maybe you already deleted root somewhere in your program?



I thought that might be it as well, but delete isn't called anywhere except for that function I posted above.

All the tNode's are dynamically created and then pushed into the vector, so it should be my responsibility to clean them up.

As for everyone suggesting Boost; I'm not a huge fan of the boost library, I understand it can make things like this easier, but I'd rather do it the old fashion way and find out WHY this is crashing instead of going around it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"As for everyone suggesting Boost; I'm not a huge fan of the boost library, I understand it can make things like this easier, but I'd rather do it the old fashion way and find out WHY this is crashing instead of going around it."

That's the right attitude. You might want to consider moving to smart pointers once you have solved the problem, despite the slightly less-natural syntax.

Share this post


Link to post
Share on other sites
I figured out the problem. It was related to that root pointer.

I use a very basic sorted list for this AI application. The sort function looks like this:


// If our list is empty
if(m_Open.empty())
m_Open.push_front(pNewNode); // Add them to the front

// Otherwise, for each item in the list...
for(list<tNode*>::iterator iter = m_Open.begin(); iter != m_Open.end(); iter++)
{
// Is this node better than one in the list?
if(pNewNode->tCost < (*iter)->tCost)
{
m_Open.insert(iter, pNewNode); // Yes, insert it
return;
}
}
// Node goes to the back
m_Open.push_back(pNewNode);




As you can see I make a bit of a special case for the 1st node placed into the list. Going on this hunch I decided to just remove this section of code:


// If our list is empty
if(m_Open.empty())
m_Open.push_front(pNewNode); // Add them to the front




And behold, it doesn't crash any longer. As to why this was corrupting, or deleteing, my root node - I don't know, but the issue is solved. The debugger does toss out a few first-chance exceptions in the output window, but it handles it gracefully(i.e. doesn't crash) so I'm not too worried.

I do appreciate all the advice so far, and will look into smart pointers and such in the future.

EDIT: Fixed the first-chance exceptions, no errors at all any longer.

Share this post


Link to post
Share on other sites
While I disagree with most of the AP's other comments (on the grounds that they're mostly stylistic, and there's no accounting for taste), I'm generally of the same opinion on this particular issue.

Smart pointers and all that are wonderful, but using them in place of regular pointers without at least some knowledge of pointers is usually just asking for trouble (not that I'm accusing the OP of not knowing anything about pointers, I'm just making a general statement) down the line.

Furthermore, a solution that is not predicated on the cause of the problem is not a solution at all, it's just a band-aid (and here the OP, AP and I agree). Especially since "_BLOCK_TYPE_IS_VALID" errors often imply a memory over- or under-write, which a smart pointer doesn't protect you against. A double-delete (which a smart pointer can protect against) is also a possibility. The OP's problem is likely one of the two, and if the former it won't be in the delete code but rather some other portion of the algorithm.

Fix the problem first, and then consider preventative measures like smart pointers in the future.

Share this post


Link to post
Share on other sites

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