Sign in to follow this  
Mizipzor

std::list::remove() not removing

Recommended Posts

I have some problems where an object from my std::list isnt removed. Could anyone help me figure out why?
	
std::list<AStarNode>	m_openList;
std::list<AStarNode>	m_closedList;

/** 
	Loops through the m_openList, finds the node with the lowest f,
	removes it from the open list, adds it to the closed list and
	returns a pointer to it.
*/
AStarNode* AStarEngine::getNextNode()
{
	AStarNode *best = &m_openList.front();

	std::list<AStarNode>::iterator i = m_openList.begin();
	for(i++; i != m_openList.end(); i++)
	{
		if((*i).f() < best->f())
		{
			best = &(*i);
		}
	}

	m_openList.remove(*best);       // 'best' isnt removed
	m_closedList.push_back(*best);
	return best;
}


Anyone that knows the astar algorihm should be able too see why I have this funcation. 'best' is added to the closed list but not removed from the open list. I have made the AStarNode myself, do it need some == operator or something for std::list to find it? I dont get any compile errors.

Share this post


Link to post
Share on other sites
erase takes an iterator to the position - not a value to erase. Try m_openList.erase(best);.

EDIT: Retrospective quote of later post:

Quote:
Original post by Palidine
Unbeliver is correct but i don't think his fix will work.


This may be right - I really do mean just 'try'. I know iterators are essentially a wrapper round the pointer - but I'm unsure if you can use a pointer as an iterator.

Share this post


Link to post
Share on other sites
Hmm... that shouldn't even compile. list<>::erase() takes an iterator, not a value. list<>::remove() takes a value, but using it would be stupid because it goes through the whole list searching the value -- something that you just did yourself! Just make best an iterator instead of a pointer, then pass it to the fast erase() function.

Share this post


Link to post
Share on other sites
Unbeliver is correct but i don't think his fix will work. try this instead:

I haven't thought all the way through it but it should be at least 90% ok. =)


AStarNode* AStarEngine::getNextNode()
{
AStarNode *best = &m_openList.front();

//hold the iterator so you can erase it
//initialize to .end in canse you never get into your if block
std::list<AStarNode>::iterator bestIt = m_openList.end();

std::list<AStarNode>::iterator i = m_openList.begin();
for(i++; i != m_openList.end(); i++)
{
if((*i).f() < best->f())
{
best = &(*i);
bestIt = i;
}
}

if ( bestIt != m_openList.end() )
{
m_openList.erase(bestIt);
m_closedList.push_back(*best);
}
return best;
}




[EDIT:

oh, also. you never want to have a .end() call in your for loop logic if you can avoid it. it's an "expensive" call. do this instead


std::list<AStarNode>::iterator ite = m_openList.end();
for( ; i != ite; i++)
{
//snip
}



and also.... why do you have an i++ in the first statement of your for loop? that means you'll never ever check the first entry in m_openList.

-me

Share this post


Link to post
Share on other sites
Hmm... no, that dont compile. I thought I changed that... oh well, it was the remove() I intended to ask about. But if that is slow, I think Ill change it to erase().

Edited, my initial post to.

Edit: Thanks for the advice Palidine, Ill try to cut out .end().

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
and also.... why do you have an i++ in the first statement of your for loop? that means you'll never ever check the first entry in m_openList.


nevermind. figured that out... in which case the code can be simpler:


AStarNode* AStarEngine::getNextNode()
{
//hold the iterator so you can erase it
//initialize to .end in canse you never get into your if block
std::list<AStarNode>::iterator best = m_openList.end();

std::list<AStarNode>::iterator i = m_openList.begin();
std::list<AStarNode>::iterator ite = m_openList.begin();
for( ; i != ite; ++i)
{
if((*i).f() < (*best).f())
{
best = i;
}
}

m_openList.erase(best);
m_closedList.push_back(*best);
return &(*best);
}





You may also want to change your lists to be std::list<AStarNode*> instead of std::list<AStarNode>. depending on the size of AStarNode you'll end up spending a great deal of CPU time copying the entire struct.

Also, it'd require performance profiling, but switching to std::vector could avoid a lot of cache misses. You may have to .reserve() memory however to avoid the memcpy costs of push_back into a full'ish vector.

-me

Share this post


Link to post
Share on other sites
You are making things too complicated. Stop thinking in terms of pointers. Think in terms of the iterators. They're smarter than pointers. Besides which, you would have needed - for correct code - to insert into the closed list first and *then* remove from the open list, because erasing something from a list would destroy it, and then there is nothing there to copy into the closed list.

Regardless, there is a much more elegant way to move something from one list to another: the 'splice' member function.

There's also a way provided in the standard library to locate the "smallest" (in our case, having the lowest f value) item in a sequence: std::min_element. All we need to do is implement the proper comparison operation.


#include <algorithm> // for std::min_element.

typedef std::list<AStarNode> nodelist;

// I assume these are members of AStarEngine!
nodelist m_openList;
nodelist m_closedList;

// We define that AStarNodes should be compared according to their f values:
bool AStarNode::operator<(const AStarNode& other) const {
return f < other.f;
}

AStarNode* AStarEngine::getNextNode() {
// Maybe you have some other handling in mind for the case when the open list
// is empty? Certainly the original code doesn't do anything about it - note
// that for an empty list, .begin() == .end(), and you can't dereference it.
assert (!m_openList.empty());
m_closedList.splice(m_closedList.end(), m_openList,
std::min_element(m_openList.begin(), m_openList.end()));
return &(m_closedList.back());
}


Yes, it's really that easy. (Although even returning a pointer may be overcomplicating things. It makes sense if you're planning to handle an empty open-list by returning NULL, say; but otherwise, you might do better to return a reference...)

std::list::splice() (scroll down to "New Members")

std::min_element

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