🔒 Locked

Std::List item removal

Started by Hornet108 Apr 27, 2006 at 11:12 AM 21 replies 2.1k views

Original Post

Apr 27, 2006 at 11:12 AM

Hi everyone In my game, I have a standard list which I iterate through each update and run each object in the lists update function. The list is part of an object manager, which does things like find targets, store and delete objects etc all from this one list. Unfortunatly I have run into a problem. When an object is destroyed or expires and needs to be removed from the list, it leaves a invalid element where the old element used to be. I have tried swaping and pop_back'ing to no avail. What I would really love to be able to do is to remove an object from the list, and then to update the list so as to no longer contain the invalid element. Heres the code I use to remove the object:


void objectmanager::removeobject(Ogre::String objectname)
{
	//broken - its leaving blank feilds in the list, which the update function is hitting and dieing on.
	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();
	for (;objectbegin != listofobjects.end(); objectbegin++)
	{

		if ((*objectbegin)->getName() == objectname)
		{
			listofobjects.erase(objectbegin);
			std::swap(objectbegin,listofobjects.end());
			listofobjects.pop_back();
		}

	}
}

Heres one of the functions which access's the list:


void objectmanager::updateObjects(float deltaT)
{
	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();
	for  (;objectbegin != listofobjects.end(); objectbegin++)
	{
		
		{
			(*objectbegin)->update(deltaT);
		}

	}
}

when the update function rolls round to the position of the old data, it hits null values and the whole program dies. Im in dire straights... please help!

Zakwayda

Apr 27, 2006 at 11:30 AM

Quote:

Original post by Hornet108
Heres the code I use to remove the object:

void objectmanager::removeobject(Ogre::String objectname){	//broken - its leaving blank feilds in the list, which the update function is hitting and dieing on.	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	for (;objectbegin != listofobjects.end(); objectbegin++)	{		if ((*objectbegin)->getName() == objectname)		{			listofobjects.erase(objectbegin);			std::swap(objectbegin,listofobjects.end());			listofobjects.pop_back();		}	}}

Try:

std::list<BaseEntity*>::iterator iter = listofobjects.begin();while (iter != listofobjects.end()) {    if ((*iter)->getName() == objectname) {        delete *iter; // Only if you actually want to delete the pointed-to object        iter = listofobjects.erase(iter);    } else {        ++iter;    }}

There are other things that could be done here, such as std::remove_if() with an appropriate predicate, and/or use of smart pointers for better pointer management.

Hornet108

Apr 27, 2006 at 11:36 AM

Hi!

Thanks for your input... however we are still having the same problem.

Simply erasing the element from the list still leaves a blank invalid element, which destroys the update function or any other function that iterates through the list.

I really need a way to bridge the node before and after the removed element, removing the null element from the list by having no node refrence it as its next or previous node.

Enigma

Apr 27, 2006 at 11:41 AM

Your algorithm is sound but your implementation is slightly wrong:

Quote:
Original post by Hornet108
std::swap(objectbegin,listofobjects.end());

This swaps the iterators, not the elements they reference. You instead want:

std::swap(<font color="red">*</font>objectbegin, listofobjects.<font color="red">back</font>());

Or, more concisely and (depending on experience with the SC++L and Boost) expressively:

listofobjects.remove_if(boost::bind(std::equal_to< Orge::String >(), boost::bind(&BaseEntity::getName, _1), objectname));

Σnigma

Zakwayda

Apr 27, 2006 at 11:48 AM

Quote:
Original post by Hornet108
Simply erasing the element from the list still leaves a blank invalid element, which destroys the update function or any other function that iterates through the list.

I really need a way to bridge the node before and after the removed element, removing the null element from the list by having no node refrence it as its next or previous node.

Not sure what you mean by this. The suggested methods should remove the node in question from the list; they don't leave a 'blank' node. If you're still having a problem, you could re-post your revised code; maybe there's still a mistake somewhere.

Evil Steve

Apr 27, 2006 at 11:49 AM

I don't understand the problem. It looks like you're not not using erase properly, since it returns an iterator to the next valid element, which you seem to be ignoring, and carrying on with your iteration using an invalid iterator...

Erasing an element in a list removes it from the list. It doesn't leave it in an invalid state or anything.

Enigma

Apr 27, 2006 at 11:57 AM

Oops, I hadn't noticed the call to erase in your loop. I glanced over it and thought you were just deleting the pointer. If you removed that line and made the change I suggested to the std::swap line then it should work. Or use jyk's version or my one. If that still doesn't work then, as jyk and Evil Steve say, we need more details.

Σnigma

Hornet108

Apr 27, 2006 at 11:26 PM

Okey, heres what I got:

objectmanager &objectmanager::instance(){	static objectmanager tempobjectmanager;	return tempobjectmanager;}void objectmanager::addobject(BaseEntity *entity){	objectnumber++;	listofobjects.push_back(entity);}void objectmanager::updateObjects(float deltaT){	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	int whereamI(0);	for  (;objectbegin != listofobjects.end(); objectbegin++,whereamI++)	{			(*objectbegin)->update(deltaT);	}}void objectmanager::removeobject(Ogre::String objectname){	//broken - its leaving blank feilds in the list, which the update function is hitting and dieing on.	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	for (;objectbegin != listofobjects.end(); objectbegin++)	{		if ((*objectbegin)->getName() == objectname)		{			objectbegin = listofobjects.erase(objectbegin);		}	}}

The removeobject function seems to be working properly now, but the update function is crashing after its been run. The game is fine until you try and remove a object from the list, so the updates are working. Things are moving around and mining and stuff, but as soon as a shot is fired, the shot reaches its destination and removeobject is called on the shot. This is done, however next time the update loop comes round, and right at the end of the loop it crashes and burns.

There is some intresting data in the debugger to note:

+	listofobjects	{size=12}	std::list<BaseEntity *,std::allocator<BaseEntity *> >-	objectbegin	{...}	std::list<BaseEntity *,std::allocator<BaseEntity *> >::iterator-	std::list<BaseEntity *,std::allocator<BaseEntity *> >::const_iterator	{_Ptr=0xfeeefeee {_Next=??? _Prev=??? _Myval=??? } }	std::list<BaseEntity *,std::allocator<BaseEntity *> >::const_iterator+	std::_Bidit<BaseEntity *,int,BaseEntity * const *,BaseEntity * const &>	{...}	std::_Bidit<BaseEntity *,int,BaseEntity * const *,BaseEntity * const &>-	_Ptr	0xfeeefeee {_Next=??? _Prev=??? _Myval=??? }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Next	CXX0030: Error: expression cannot be evaluated	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Prev	CXX0030: Error: expression cannot be evaluated	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Myval	CXX0030: Error: expression cannot be evaluated	BaseEntity *	whereamI	13	int

What appears to be happening is that the update function is continuing to iterate through the list as if it had not been modified - it doesent seem to know that the list has been shortened and as such is it reaching for that final element which just is no longer there. As to why this is happening, im stumped. Maybe im on the wrong track alltogether however I dont think so.

Again, any help is greatly appreciated.

Fruny

Apr 27, 2006 at 11:46 PM

Erase invalidate iterators. After listofobjects.erase(objectbegin);, doing objectbegin++ is illegal. Instead, do objectbegin = listofobjects.erase(objectbegin); and do not increment.

This behaviour is fully documented.

Verg

Apr 28, 2006 at 12:14 AM

Quote:
Original post by Fruny
Erase invalidate iterators. After listofobjects.erase(objectbegin);, doing objectbegin++ is illegal. Instead, do objectbegin = listofobjects.erase(objectbegin); and do not increment.

This behaviour is fully documented.

@ OP:

In other words, turn this:

for (;objectbegin != listofobjects.end(); objectbegin++){	if ((*objectbegin)->getName() == objectname)	{		objectbegin = listofobjects.erase(objectbegin);	}}

into this:

for (;objectbegin != listofobjects.end();){	if ((*objectbegin)->getName() == objectname)	{		objectbegin = listofobjects.erase(objectbegin);	}	else ++objectbegin;}

Hornet108

Apr 28, 2006 at 12:34 AM

Thanks a bunch guys, but its not actually the removeobject function thats broken...

Even with your changes copy pasted in, im still having the same error on the updateobjects function.

However, from what I am coming to understand now from this thread is that once you erase an object from a list, you cannot iterate through it again. Is this correct?

RDragon1

Apr 28, 2006 at 12:39 AM

What good would that be? No, it's not correct. Is this multithreaded code or something?

You're probably not reading the code carefully. Study very carefully the code that Varg posted. If you've still got your increment there in the for(;;) statement you're bound to end up with problems.

Verg

Apr 28, 2006 at 12:41 AM

[EDIT] D'oh! Too slow.

Quote:
Original post by Hornet108
Thanks a bunch guys, but its not actually the removeobject function thats broken...

Even with your changes copy pasted in, im still having the same error on the updateobjects function.

However, from what I am coming to understand now from this thread is that once you erase an object from a list, you cannot iterate through it again. Is this correct?

That would make the std containers pretty useless, eh? :)

No, you can iterate through the list all you want as long as you don't invalidate the iterator while doing so.

About "updateobjects" code... I'm not seeing anything obvious... maybe it has something to do with the "update" function itself.

Could be a threading issue, too. Could be lots of things :)

Take care.

Chad

Palidine

Apr 28, 2006 at 12:42 AM

Quote:
Original post by Hornet108
However, from what I am coming to understand now from this thread is that once you erase an object from a list, you cannot iterate through it again. Is this correct?

No. All they are saying is that when you erase an iterator from the list, that very iterator is no longer valid:

std::list<MyClass> myList;std::list<MyClass>::iterator it = myList.begin();myList.erase(it);//if you try to use 'it' now, it's an error, because 'it' now contains invalid data

there should be no errors with the code that people are posting. post your code again. The last time you pasted in code, you didn't actually implement the code correctly.

-me

Hornet108

Apr 28, 2006 at 12:57 AM

The bold line bellow is where it is breaking. This function only breaks once the removeobject function has removed an object from the list.

void objectmanager::updateObjects(float deltaT){	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	int whereamI(0);	for  (;objectbegin != listofobjects.end(); objectbegin++,whereamI++)	{			(*objectbegin)->update(deltaT);	}}void objectmanager::removeobject(Ogre::String objectname){	//broken - its leaving blank feilds in the list, which the update function is hitting and dieing on.	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	for (;objectbegin != listofobjects.end();)	{		if ((*objectbegin)->getName() == objectname)		{			objectbegin = listofobjects.erase(objectbegin);		}		else ++objectbegin;	}}

is returning an access violation.

Data of intrest:

-	_Myhead	0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 {_Next=0x034e6680 _Prev=0x034e65f0 _Myval=0x004c2060 } _Prev=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Myval=0x004c22a0 class resourcecluster newresource } _Prev=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Prev=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={...} ...} } _Myval=0x004c1f28 class drone newdrone } _Prev=0x034f8130 {_Next=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Prev=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={...} ...} } _Prev=0x034e6878 {_Next=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Prev=0x034e6830 {_Next=0x034e6878 _Prev=0x034e67e8 _Myval=0x004c2360 } _Myval=0x004c1e48 class Building newbuilding } _Myval=0x034e68c0 {m_OwnerId=-842150451 timeonstation=0.00000000 carrying=true ...} } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={x=??? y=??? z=??? ...} ...} }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *-	_Next	0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 {_Next=0x034e6680 {_Next=0x034e66c8 _Prev=0x034e6638 _Myval=0x004c2420 } _Prev=0x034e65f0 {_Next=0x034e6638 _Prev=0x034e65a8 _Myval=0x004c22a0 } _Myval=0x004c2060 class resourcecluster newresource2 } _Prev=0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 _Prev=0x034e65a8 _Myval=0x004c22a0 } _Prev=0x034e6560 {_Next=0x034e65a8 _Prev=0x034f8130 _Myval=0xcdcdcdcd } _Myval=0x004c1f28 class drone newdrone } _Myval=0x004c22a0 class resourcecluster newresource } _Prev=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 _Prev=0x034e65a8 _Myval=0x004c22a0 } _Prev=0x034e6560 {_Next=0x034e65a8 _Prev=0x034f8130 _Myval=0xcdcdcdcd } _Myval=0x004c1f28 class drone newdrone } _Prev=0x034f8130 {_Next=0x034e6560 {_Next=0x034e65a8 _Prev=0x034f8130 _Myval=0xcdcdcdcd } _Prev=0x034e6878 {_Next=0x034f8130 _Prev=0x034e6830 _Myval=0x004c1e48 } _Myval=0x034e68c0 {m_OwnerId=-842150451 timeonstation=0.00000000 carrying=true ...} } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={x=??? y=??? z=??? ...} ...} } _Myval=0x004c1f28 class drone newdrone }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Next	0x034e65f0 {_Next=0x034e6638 {_Next=0x034e6680 {_Next=0x034e66c8 {_Next=0x034e6710 _Prev=0x034e6680 _Myval=0x004c2120 } _Prev=0x034e6638 {_Next=0x034e6680 _Prev=0x034e65f0 _Myval=0x004c2060 } _Myval=0x004c2420 class resourcecluster newresource3 } _Prev=0x034e65f0 {_Next=0x034e6638 {_Next=0x034e6680 _Prev=0x034e65f0 _Myval=0x004c2060 } _Prev=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Myval=0x004c22a0 class resourcecluster newresource } _Myval=0x004c2060 class resourcecluster newresource2 } _Prev=0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 {_Next=0x034e6680 _Prev=0x034e65f0 _Myval=0x004c2060 } _Prev=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Myval=0x004c22a0 class resourcecluster newresource } _Prev=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Prev=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={...} ...} } _Myval=0x004c1f28 class drone newdrone } _Myval=0x004c22a0 class resourcecluster newresource }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Prev	0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 {_Next=0x034e6680 _Prev=0x034e65f0 _Myval=0x004c2060 } _Prev=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Myval=0x004c22a0 class resourcecluster newresource } _Prev=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Prev=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={...} ...} } _Myval=0x004c1f28 class drone newdrone } _Prev=0x034f8130 {_Next=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 _Prev=0x034e6560 _Myval=0x004c1f28 } _Prev=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={...} ...} } _Prev=0x034e6878 {_Next=0x034f8130 {_Next=0x034e6560 _Prev=0x034e6878 _Myval=0x034e68c0 } _Prev=0x034e6830 {_Next=0x034e6878 _Prev=0x034e67e8 _Myval=0x004c2360 } _Myval=0x004c1e48 class Building newbuilding } _Myval=0x034e68c0 {m_OwnerId=-842150451 timeonstation=0.00000000 carrying=true ...} } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={x=??? y=??? z=??? ...} ...} }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Myval	0x004c1f28 class drone newdrone	BaseEntity *+	_Prev	0x034f8130 {_Next=0x034e6560 {_Next=0x034e65a8 {_Next=0x034e65f0 {_Next=0x034e6638 _Prev=0x034e65a8 _Myval=0x004c22a0 } _Prev=0x034e6560 {_Next=0x034e65a8 _Prev=0x034f8130 _Myval=0xcdcdcdcd } _Myval=0x004c1f28 class drone newdrone } _Prev=0x034f8130 {_Next=0x034e6560 {_Next=0x034e65a8 _Prev=0x034f8130 _Myval=0xcdcdcdcd } _Prev=0x034e6878 {_Next=0x034f8130 _Prev=0x034e6830 _Myval=0x004c1e48 } _Myval=0x034e68c0 {m_OwnerId=-842150451 timeonstation=0.00000000 carrying=true ...} } _Myval=0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={x=??? y=??? z=??? ...} ...} } _Prev=0x034e6878 {_Next=0x034f8130 {_Next=0x034e6560 {_Next=0x034e65a8 _Prev=0x034f8130 _Myval=0xcdcdcdcd } _Prev=0x034e6878 {_Next=0x034f8130 _Prev=0x034e6830 _Myval=0x004c1e48 } _Myval=0x034e68c0 {m_OwnerId=-842150451 timeonstation=0.00000000 carrying=true ...} } _Prev=0x034e6830 {_Next=0x034e6878 {_Next=0x034f8130 _Prev=0x034e6830 _Myval=0x004c1e48 } _Prev=0x034e67e8 {_Next=0x034e6830 _Prev=0x034e67a0 _Myval=0x004c1c08 } _Myval=0x004c2360 class resourcecluster newresource9 } _Myval=0x004c1e48 class Building newbuilding } _Myval=0x034e68c0 {m_OwnerId=-842150451 timeonstation=0.00000000 carrying=true ...} }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Myval	0xcdcdcdcd {firsttime=??? m_velocity=??? m_Position={x=??? y=??? z=??? ...} ...}	BaseEntity *	_Mysize	12	unsigned int-	objectbegin	{...}	std::list<BaseEntity *,std::allocator<BaseEntity *> >::iterator-	std::list<BaseEntity *,std::allocator<BaseEntity *> >::const_iterator	{_Ptr=0xfeeefeee {_Next=??? _Prev=??? _Myval=??? } }	std::list<BaseEntity *,std::allocator<BaseEntity *> >::const_iterator+	std::_Bidit<BaseEntity *,int,BaseEntity * const *,BaseEntity * const &>	{...}	std::_Bidit<BaseEntity *,int,BaseEntity * const *,BaseEntity * const &>-	_Ptr	0xfeeefeee {_Next=??? _Prev=??? _Myval=??? }	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Next	CXX0030: Error: expression cannot be evaluated	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Prev	CXX0030: Error: expression cannot be evaluated	std::_List_nod<BaseEntity *,std::allocator<BaseEntity *> >::_Node *+	_Myval	CXX0030: Error: expression cannot be evaluated	BaseEntity *	whereamI	13	int

Palidine

Apr 28, 2006 at 1:02 AM

The removal code is fine. My guess is you have bad pointers in there. Post the code where you are adding items to the list.

As a side note, if you are new'ing the pointers into the list you have to delete them during the removal step:

//made a few tweaks to tidy up your codevoid objectmanager::removeobject(const Ogre::String &objectname){	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	while (objectbegin != listofobjects.end())	{		if ((*objectbegin)->getName() == objectname)		{			delete (*objectbegin);  // <---- you MUST do this if this class "owns" the pointers			objectbegin = listofobjects.erase(objectbegin);		}		else		{			++objectbegin;		}	}}

Hornet108

Apr 28, 2006 at 1:06 AM

the function that adds data is fairly straight forward:

void objectmanager::addobject(BaseEntity *entity){	objectnumber++;	listofobjects.push_back(entity);}

Palidine

Apr 28, 2006 at 1:07 AM

Wait. Does your BaseEntity::update function (or any of it's derive class's update functions) have the possibility to call the remove function somewhere within their scope? If so that's your problem.

-me

Palidine

Apr 28, 2006 at 1:08 AM

Quote:
Original post by Hornet108
the function that adds data is fairly straight forward:
void objectmanager::addobject(BaseEntity *entity){	objectnumber++;	listofobjects.push_back(entity);}

Well, I was actually looking for the code that allocates the memory for the item that's being inserted into the list.

-me

Palidine

Apr 28, 2006 at 1:11 AM

For the purposes of debugging change your update method to this:

void objectmanager::updateObjects(float deltaT){	std::list<BaseEntity*>::iterator objectbegin = listofobjects.begin();	int whereamI(0);	for  (;objectbegin != listofobjects.end(); objectbegin++,whereamI++)	{		BaseEntity *entity = *objectbegin;		entity->update(deltaT);	}}

entity->update(deltaT); // <--- it should crash on this line.

assuming that entity->update(deltaT) can never ever ever call removeobject, then:

If the entity pointer is == 0xcdcdcdcd then the bug is that your are pushing an uninitialized pointer into the list. So check the code where you allocate memory and then call addobject. That's where the bug is.

If the entity pointer is some other non NULL value then you are delete'ing the pointer somewhere else in your code. Look anywhere in your code where you are delete'ing BaseEntity classes or derived classes, that's where your bug is.

-me

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.