next »

[ITS_Mike]

I've been running into this design problem for a while, and it has been bugging me. I am posting it here in the hope that it will finally be resolved.

Code:

CClass *objects[MAX_OBJECTS];

void Foo()
{
	for (int i = 0; i < MAX_OBJECTS; i++)
	{
		if (objects[i] != NULL)
		{
			Bar(i);
			objects[i]->A();
		}
	}
}

At some point in Bar(), the object #i may be deleted. If this happens, everything after Bar() that tries to access object #i will fail.

I know multiple ways that this can be solved. However, because I am relatively new to code design and OOP, I don't know if there is a standard/common/best solution. I could choose one of my solutions at random, but I would rather learn what the "proper" solution is, if such a thing exists. I have not posted my own solutions here because I don't want to accidentally influence responses. If requested, I can provide my thoughts on the matter.

Please note that I am looking for an abstract solution. If the solution for this problem is dependent on the exact situation, please let me know and I will give a specific situation in which this problem is occurring.

[Draknek]

One way: add a deleteFlag property to CClass, and instead of deleting the object set the flag.

Then do a post-processing step right at the end to actually delete any object with deleteFlag set.

Another: recheck if objects[ i ] is null after any method call which might delete it.

[ThemsAllTook]

The Cocoa framework has an interesting way of dealing with (or depending on how you look at it, avoiding dealing with) this. Every object is manually reference counted, with clear ownership conventions. What they'd do to make this sort of thing possible is to add the object to an autorelease pool, which means that although its logical reference count may drop to zero, its physical reference count will still be positive until the autorelease pool is emptied. So, it essentially allows the object to live until the next return to the main run loop, at which point it's disposed by the pool.

You may be able to find a cleaner solution by taking a closer look at your object ownership rules. For example, why is Bar() actually deleting the object, while Foo is the one that owns the list of objects? Maybe that doesn't actually make sense and Foo should be the only one with the authority to delete objects from itself.

[Fallsburg]

In your effort to make everything abstract, you have abstracted away a lot of meaning.  Like ThemsAllTook said, why is Bar deleting objects?
Also, not to tell you how to code, but I would definitely recommend on using the STL container classes instead of a pointer buffer.  First of all it will be dynamically sized, getting rid of the need to loop through everything and only act on non-null objects, and only using as much memory as needed (well, depending on what container class you are using). Secondly, it takes care of a lot of things behind the scenes that you don't necessarily want to deal with.
If it is completely necessary for Bar to be deleting the objects, I would have it return a boolean saying whether it had deleted or not.  If it had then you wouldn't call "objects->A();".
 

[ITS_Mike]

Thanks for the responses so far.

I made the question abstract because that is how I want it to be taken.  The problem itself applies to many situations.  Here are a couple of them:
Network packet handling. For this example, objects are called clients and Bar() handles network packets for client #i. Among other reasons, an error in a packet could cause the client to be forcibly disconnected (and thus, the client object would be removed). The call to CClass::A() represents any code that would be executed after the client has been removed.

Another example is where Foo() is managing the characters (and possibly other things) in the game. The object is a character. Bar() represents one of possibly multiple character management functions where the character could become removed from the world due to death or other reasons specific to the game. The call to CClass::A() represents any code that would be executed after the character has been removed.

[Kaelan]

Don't access objects by index, access them by reference (via pointers).

Have only a single object responsible for the lifetime of any given object - for a hypothetical example, Map would be responsible for the lifetime of all Tiles. This gives you a way to easily look at a given piece of code and say 'is this Tile alive? Well, the Map is...'

Or, if you need to access objects by index, you can use a twist on the previous method: Have a single object responsible for the lifetime of a group of objects - for example, allocate all your Tiles at once, and don't destroy any of them until the entire group is dead.

Lifetime management isn't an abstract issue. You need to know exactly what your model is and how it's being used to decide what the right lifetime policy is. If you want good feedback you need to at least tell us the general details of what your objects are.

[st33d]

A lot of my objects have a property called "active".

If an object isn't active then it doesn't get its code processed and is due for destruction.

pseudo code:

Code:

FOR I < GAME_OBJECTS:

  IF 
    GAME_OBJECTS[I].ACTIVE THEN GAME_OBJECTS[I].MAIN

  ELSE 
    GAME_OBJECTS.REMOVE(I)
    I--

At some point during the GameObject's loop it may become inactive, but at that point I can simply call a kill() method, removing any asociated objects return from the GameObject's main method and let the GameObject get garbage collected.

[ITS_Mike]

Have only a single object responsible for the lifetime of any given object - for a hypothetical example, Map would be responsible for the lifetime of all Tiles. This gives you a way to easily look at a given piece of code and say 'is this Tile alive? Well, the Map is...'

That solved a design issue I had the other day.  Unfortunately, I found that it doesn't quite work if you are deleting them from inside of the manager.  Notice that Foo() and Bar() are part of the same "manager" (they are global in the example, not part of a class, but it amounts to the same thing).  Foo() obviously knows that itself is alive, so the problem remains.  Also, since Bar() is part of the same "manager" as Foo(), the same manager is still deleting the object itself.

Lifetime management isn't an abstract issue. You need to know exactly what your model is and how it's being used to decide what the right lifetime policy is. If you want good feedback you need to at least tell us the general details of what your objects are.

I gave a couple examples in my previous post.  These are situations that currently exist in my code.

[Fallsburg]

What sort of code do you mean by "The call to CClass::A() represents any code that would be executed after the character has been removed."?  If my interpretation of that is correct, you are trying to create some sort of extra destructor.
I stand by what I previously said. You should be using the STL container classes (most likely vector or list depending on if you need random access or not).  You should also be using a destructor in CClass a la

Code:

  CClass{
    CClass(); //Default Constructor
    ~CClass(); // Destructor, called upon deletion of an instance
  };

Unless I am misinterpreting what you intend by that CClass::A() method, the destructor should be what you are looking for.

The way I would envision your code is:

Code:

#include <list>

std::list<CClass> objects;

void Foo(){
          
	for (std::list<CClass>::iterator listIter = objects.begin();
             listIter != objects.end();
             ++listIter){
	     listIter = Bar(listIter); // The return value should either be listIter or return objects.erase(listIter), depending on whether you want to keep listIter or not
	}
}

I chose list instead of vector, because my guess is that you don't care about randomly accessing elements in objects (e.g. You want to know what element 537 of objects is), but rather you just care about looping through objects.

Note that this is only recommended for things that will have a lengthy lifetime. For things with a shorter lifespan (like your packet example, or for example projectiles in a Shoot-em-up) you would want to have some sort object pool.  That way you wouldn't constantly be creating and destroying objects (relatively time expensive if you are doing it billions of times) and instead would just activate and deactivate objects when they are needed.

If I'm misreading your intentions with CClass::A() let me know.

[Sos]

Code:

CClass *objects[MAX_OBJECTS];

void Foo()
{
	for (int i = 0; i < MAX_OBJECTS; i++)
	{
		if (objects[i] != NULL)
		{
			Bar(i);
			objects[i]->A();
		}
	}
}

Haha, that's what you get for going C in a C++ zone, silly.

Array of pointers is OK, of course (static > dynamic), but you don't get much more than a bunch of leftover crap nowhere-pointers from that, since you forgot to INITIALISE. And most of them WILL pass the null test, since pointers do not get initialised by default (some comppilers might do that tho). And Bar() does not delete your  objects, but it just uses the stack (where your objects are, until initialised), and you have to dig your objects out before accessing them again (no, don't do that).

[ITS_Mike]

Code:

CClass *objects[MAX_OBJECTS];

void Foo()
{
	for (int i = 0; i < MAX_OBJECTS; i++)
	{
		if (objects[i] != NULL)
		{
			Bar(i);
			objects[i]->A();
		}
	}
}

Haha, that's what you get for going C in a C++ zone, silly.

Array of pointers is OK, of course (static > dynamic), but you don't get much more than a bunch of leftover crap nowhere-pointers from that, since you forgot to INITIALISE. And most of them WILL pass the null test, since pointers do not get initialised by default (some comppilers might do that tho). And Bar() does not delete your  objects, but it just uses the stack (where your objects are, until initialised), and you have to dig your objects out before accessing them again (no, don't do that).

Thanks for the input, but that is little better than pseudo code.  Something I wrote to illustrate the structure of the problem.

What sort of code do you mean by "The call to CClass::A() represents any code that would be executed after the character has been removed."?

The line objects[ i]->A(); (space added to prevent BBCode) represents any code which would be executed after Bar() returns.  That line may not actually exist in practice, it is just a place holder.

[BorisTheBrave]

If you have garbage collection, or some trick to emulate it (the cocoa one sounds cool), I'd mark a "destroyed" object as destroyed then I'd copy the array before looping over it, checking the destroyed flag each time.

Otherwise, I'd create an onDestroy event for the object, and design iterators that work with that (potentially expensive).

A trick that the Box2D library I work on uses, is to use inlined linked lists, so you can navigate from one object pointer to the next. Thus maintaining valid iterators is a matter of having valid pointers to objects, which obviously you need to be doing anyway. Not that this means the problem is solved - Box2D more or less bans you from edits while it is iterating over stuff.

But AFAIK, there's no canonical solution, or even established design pattern. Most people just make sure ownership semantics are well defined, and thus there are no functions like Bar capable of doing arbitrarily complex amounts of damage.

[Fallsburg]

The line objects[ i]->A(); (space added to prevent BBCode) represents any code which would be executed after Bar() returns.  That line may not actually exist in practice, it is just a place holder.

Again, what sort of code? Do you want it to be run only if the instance at i is deleted, is not deleted , or no matter what? 

A) If you want it to be run if the instance is destroyed, the destructor is what you want.

B) If you want it to be run if the instance is not destroyed, then I'd put the call in Bar() in the return case where it isn't destroyed.

C) If you want it always to run and it relies on the instance, then you should run the code beforehand, because you obviously can't rely on the instance still being valid.

D) If you want it always to run and it doesn't rely on the instance, then by all means go ahead and run it.

Once more, check out the STL container classes.  I think you will want to go with the code that I listed and go with case A and B.

[ITS_Mike]

The line objects[ i]->A(); (space added to prevent BBCode) represents any code which would be executed after Bar() returns.  That line may not actually exist in practice, it is just a place holder.

Again, what sort of code? Do you want it to be run only if the instance at i is deleted, is not deleted , or no matter what? 

A) If you want it to be run if the instance is destroyed, the destructor is what you want.

B) If you want it to be run if the instance is not destroyed, then I'd put the call in Bar() in the return case where it isn't destroyed.

C) If you want it always to run and it relies on the instance, then you should run the code beforehand, because you obviously can't rely on the instance still being valid.

D) If you want it always to run and it doesn't rely on the instance, then by all means go ahead and run it.

Once more, check out the STL container classes.  I think you will want to go with the code that I listed and go with case A and B.

It is case C.

Thanks everyone for the input so far.  I am currently trying a few things.  If anyone has further thoughts on the matter though, please leave a post!

[Sos]

Just post the actual source.

[ITS_Mike]

Just post the actual source.

Sorry but I'm not asking for a solution to an exact code problem.  I'm looking for a solution to a design problem.  The "actual source" doesn't really exist since this problem is in multiple areas, and in some cases spans over most of the code (which I cannot release).

[Will Vale]

For "game entity" lifetime, a "dead" flag as described by other posters is a good method. Set the flag when you kill an object, then clean it up after the frame - that way you know that an object alive at the start of the frame will live through all the code which might want to use it. Another version of this is to add the object to a "dead objects" list and walk that at the end of the frame.

Even in your network client case, it might be better to set client->state to "disconnected" rather than throw everything away instantly.

For other objects, trying to get a better idea of ownership is probably a good thing. IMO most kinds of thing which aren't game entities don't have complex ownership when you get right down to it.

<rant>I'd tend to treat the well-meaning suggestions to use STL in preference to any other coding style as noise STL doesn't address the original problem, - it's not like STL iterators are deletion-safe. The question "should I use STL container X instead of a C-style array" is complex and has a lot to do with your experience level, target platforms, performance requirements and a load of other context which isn't available here.</rant>

Cheers,

Will

[Fallsburg]

<rant>I'd tend to treat the well-meaning suggestions to use STL in preference to any other coding style as noise STL doesn't address the original problem, - it's not like STL iterators are deletion-safe. The question "should I use STL container X instead of a C-style array" is complex and has a lot to do with your experience level, target platforms, performance requirements and a load of other context which isn't available here.</rant>

<rant>
Now, I know that I've been harping on it, but it isn't just noise.  While STL doesn't address the original problem as it is now understood, it addresses a whole host of other issues.  Using STL isn't a complex issue (unless you are stuck in a distinctly C mindset).  As for target platforms, I can't say anything about non-personal computer (Mac,Windows PC, Linux PC) platforms, but that is unlikely to be a concern here.  The performance requirements issue always gets brought up by people who think there is some enormous overhead to the STL library, which by and large isn't true.  Typically, by using the associated algorithms one will get far better performance, than by using the C style arrays and a naive or even non-optimized solution.

In the example we are given, if the array is of size n and has k non-NULL elements then we will be doing, n*O(1) + k*TimeComplexityOfBar, instead of just k*max(TimeComplexityOfBar,O(1)), which means that if TimeComplexityOfBar is O(1) (which for the cases he listed should be) we will be doing O(n+k) work instead of O(k) work.  Now, I imagine that the work in Bar will have far greater overhead than checking if element is null, but if k is small compared to n, we will still be doing a lot more work than needs to be.  AND that's just using the fact that we will only be looping over the actual elements, let alone actually doing some sort of algorithmic work.
</rant>

Now, I know there are exceptions to just about everything someone can say, but I truly believe that his code will wind up being much more efficient if he uses the STL library instead of trying to roll his own.  Why implement your own red-black tree, or your own introsort, when it is already done for you (besides educational purposes)?

As for what it seems like he actually needs, then I would say a list or vector and have the dead/alive flag and then the clean-up step.

[oahda]

For my current project, I've been using the STL vector just because of lazyness and currently I don't need anything fancy, but I've actually constructed my own vector class (as well as working on strings, file handling and a lot of other basic but important things) just to get my tools exactly the way I want them. One can easily shuffle the elements of my vectors, for example, and the string class has explicit C string conversion, and a shitload of member functions (such as split, splitting into a vector of my own class, join, find, count instances of letters or words, reduce duplicate characters and a lot of stuff).

That's also an option.

[Will Vale]

While STL doesn't address the original problem as it is now understood,

That's really what I was getting at - in the context of this thread, the STL suggestions are a bit noisy

On the original point, I guess it helps to think about object lifetime (in a C++ mechanical new-and-delete sense) as something quite different from entity lifetime. If a baddy gets squished by spikes, you probably don't delete it straight away - there could be a death animation to play, plus other things might be looking at it. You might even recycle the C++ object for a different game entity.

Will