Sign in to follow this  

[Solved] (C++) Problem with std::list iterators

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

I'm getting assertion failures when I run my code, and they orignate in these two functions... I know I'm doing something wrong with my iterators, I just can't figure out what. (it doesn't help that the iterators are pointing to pointers) HookEntity() takes an entity and stores its address in the list, then sets its itr member to the location of ent'd address in the list. UnhookEntity() takes the aforementioned itr member of an entity and replaces the list location with a NULL pointer (if it's at the end of the list, it just pop_back()'s it off)
void GameView::HookEntity(entity& ent)
{
	if (ent.itr._Ptr != NULL)
		return;

	std::list<entity*>::iterator itr = entities.begin();
	for (; itr != entities.end(); ++itr)
	{
		if (*itr == NULL)
			break;
	}

	if (itr == entities.end())
	{
		entities.push_back(&ent);
		ent.itr = --entities.end();
	}
	else
	{
		*itr = &ent;
		ent.itr = itr;
	}
}

void GameView::UnhookEntity(std::list<entity*>::iterator& itr)
{
	if (*itr == NULL)
		return;

	std::list<entity*>::iterator ent = std::find(entities.begin(), entities.end(), *itr);

	if (ent == entities.end())
		return;
	else if (ent == --entities.end())
		entities.pop_back();
	else
		*ent = 0;

	*itr = NULL;
}


[Edited by - Twisol on June 21, 2008 4:27:37 PM]

Share this post


Link to post
Share on other sites
It looks like you're storing the iterator pointing to an entity in the entity itself. My guess it that you're using that iterator to unhook the entity later.

However, iterators become invalid after modifying the list, so the moment you push_back() or pop_back(), all iterators stored in all entities in that list become invalid, so something will go wrong during UnhookEntity().

Edit: on second thought, I'm not sure iterators become invalid for a std::list.

Edit 2: on closer inspection, I suspect the problem lies in the last statement of UnhookEntity. When you're unhooking the last entity in the list, you pop_back(), invalidating the iterator ent. But this is the same iterator as itr, so doing *itr = NULL afterwards will be invalid. You could just remove that last statement. Also, as a side note, the _Ptr isn't very portable I suspect.

Another way is to search the array for the entity address. You could also change it to a std::set to reduce the complexity (it would also simplify the whole thing):


void GameView::HookEntity(entity& ent)
{
entities.insert(&ent);
}

void GameView::UnhookEntity(entity& ent)
{
entities.erase(&ent);
}





Or use another approach alltogether ;)

Share this post


Link to post
Share on other sites
Why are you storing pointers in your std::list instead of the objects themselves?

Also, why does the unhook function replace the entry with a NULL pointer instead of just deleting the node? You know deleting nodes from a linked list is a constant time operation right?

Share this post


Link to post
Share on other sites
I only store pointers in the list because I keep the entities themselves stored somewhere else. I can modify the entities directly instead of having to muck through the list and find a specific entity every time I want to change something, like the position of the entity.

I replace the pointer in the list with a NULL pointer in UnhookEntity so I don't invalidate the iterators further up in the list, although you're right, I don't think list iterators are invalidated like that. I guess I can probably get rid of that, hehe.

I've changed the code, and it looks cleaner (and works too!). Now, if itr._Ptr isn't portable, then I'm not sure how to make my iterator point to NULL.



void GameView::HookEntity(entity& ent)
{
if (ent.itr._Ptr != NULL)
return;

entities.push_back(&ent);
ent.itr = --entities.end();
}

void GameView::UnhookEntity(std::list<entity*>::iterator& itr)
{
if (itr._Ptr == NULL)
return;

// check that the iterator points to a node in this list
std::list<entity*>::iterator ent = std::find(entities.begin(), entities.end(), *itr);

if (ent == entities.end())
return;
else
entities.erase(itr);

itr._Ptr = NULL;
}





EDIT: Molle85, entities.end() has versions that return either a const iterator or a non-const iterator. Since I'm not geting errors I'm going to assume that it's returning a non-const iterator. (Although, technically I wouldn't be using the iterator in my entity structuers to modify anything directly, so maybe it would better off const anyways..)

Share this post


Link to post
Share on other sites
Is end() guarenteed to be the same no matter how many nodes the list contains? Also, it appears (at least in my implementation) that itr._Ptr is initialized at 0x0000000, so it would be preferrable to base my checks on that rather than end().

Share this post


Link to post
Share on other sites
If you're storing, within the Entity class, an iterator that points to a corresponding element in a container that stores entities, then that's probably bad. If you're accessing internal, implementation-specific data of an iterator object, then that's probably bad as well.

A general rule of thumb is that objects should not know about the containers that hold them. One reason for this (and there are probably several good ones) is that it decreases modularity by tying the object type and the container type together. (In other words, you lose flexibility - what if you want to create a temporary object that isn't stored in a container? What if you want to store different objects of the specified type in containers of different types?)

As for the iterator manipulation you're doing, I'm not sure what you're trying to achieve, but generally speaking you should interact with containers and iterators through their published interfaces, or through free functions. Whatever you need to do - remove an object, add an object, move an object to a different location - there's a way to do it without storing iterators within the class itself or mucking about with the iterator internals.

Finally, a typical solution to the type of object ownership problem you seem to be dealing with here is to use a smart pointer of some type. In C++, the most common solution in use these days is probably boost::shared_ptr.

Beyond that, it's difficult to offer more specific advice without knowing more about what you're doing. Can you provide more details? What does the entity list in question represent? And who owns the entities?

Share this post


Link to post
Share on other sites
I'm storing a list of entity pointers, and the user of the GameView owns the entities. The user can modify the data in the entity struct, and the GameView doesn't need to know you changed it; all the GameView does is take the entity data and use it to place the entity on the screen.

If you wanted to create an entity that's not stored in the container, that's fine. The user isn't supposed to touch the stored iterator except to pass to UnhookEntity(), although if I can get away with passing the address of the entity instead, I'll do that. (Coding late at night has its drawbacks)


EDIT: I've gotten rid of the iterator member in the entity and I'm searching by the address of the entity now. Here's the code, it looks good and it looks like it works!



void GameView::HookEntity(entity& ent)
{
// make sure there is no duplicate entity* in the list
std::list<entity*>::iterator itr = std::find(entities.begin(), entities.end(), &ent);
if (itr != entities.end())
return;

entities.push_back(&ent);
}

void GameView::UnhookEntity(entity& ent)
{
// make sure the entity* is in the list
std::list<entity*>::iterator itr = std::find(entities.begin(), entities.end(), &ent);
if (itr == entities.end())
return;

entities.erase(itr);
}


Share this post


Link to post
Share on other sites

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