• Create Account

Dangling pointers in vectors

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

14 replies to this topic

#1stillLearning()  Members

Posted 23 September 2012 - 04:47 PM

Hi there.

First thread on GameDev. First I shall say I am somewhat confused about my problem, hence my description might be lacking or difficult to understand. Ill try my best. In my game I have vectors of pointers to different objects, IE enemies & trees etc.

vector<Object*> allObjects;

void addObject(Unit* obj)
{
allObjects.push_back(obj);
}

addObject(new Unit(...));
Using addObject allocates an Unit to allObjects. So far everything is fine.

During the lifetime of the Unit, lots of pointers to this Unit is created at several different locations in my program. Now when this particular Unit is deallocated, I end up having lots of vectors with dangling pointers.

The only way Ive come up with to solve this is to manually keep track of every single vector containing a pointer to the Unit by having a Vector of Vectors of Units.
[source lang="cpp"]vector<vector<Unit*>* > existsInVectors;[/source]
and then in the destructor of Unit calling existsInVectors.erase(iterator to Unit). For every "send unit to vector"-function, I need to call a "RemindUnitOfThisVector"-function... I find this solution ugly, inefficient and difficult to maintain...

What would be an efficient way of having multiple vectors pointing to an instance of Unit without manually tracking what vectors the Unit is stored in? If only vectors did autoerase on dangling pointers...

If you don't understand the stuff written here, please sharpen your C++ skills.

#2kd7tck  Members

Posted 23 September 2012 - 05:43 PM

The easiest way is to doubly link everything, this is easier because it will require the least modification to your program. To implement, make sure every object that has a vector is also part of a vector collection in each of the child objects. This must be made a constant for every vector, if you choose to do it this way. Later when the deconstructor of an object is called, it will contact each and every child object in it's vector and remove itself from their vectors.

Otherwise you can use modified smart pointers, that take into account all vector copies.

#3Matt-D  Members

Posted 23 September 2012 - 05:46 PM

Either use a container of smart pointers or a (smart) pointer container (if these two options sound similar, it's because they are, but there are some differences and trade-offs involved; you can also consider a variation thereof like a shared_array); here are some of your options:
Boost Smart Pointers: http://www.boost.org/libs/smart_ptr/
C++ 11 Smart Pointers: http://en.cppreferen...om/w/cpp/memory
Boost Pointer Container Library: http://www.boost.org.../ptr_container/

Edited by Matt-D, 23 September 2012 - 06:08 PM.

#4Goran Milovanovic  Members

Posted 23 September 2012 - 09:23 PM

During the lifetime of the Unit, lots of pointers to this Unit is created at several different locations in my program.

Redesign the system to avoid that inconvenient circumstance.

I don't know what you're trying to do, but I suspect that there's really no good reason to keep all those pointers scattered around.

+---------------------------------------------------------------------+

| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+

#5stillLearning()  Members

Posted 24 September 2012 - 02:15 AM

I have done some research on this problem and as you guys suggest it seems Boost::shared_ptr is the way to go. I have trouble understanding why boost libraries would solve my problem though.

If I have a vector of shared_ptr whereas one of the shared_ptrs are pointing to object Foo, and Foo is deleted, does the vector erase the element with a shared_ptr to Foo? From what I understood this is not the case, and hence not a solution to my problem... Although it is very likely I have misunderstood the concept of shared_ptr. To me it seems that shared_ptr can be dangling aswell since the vector still has an element where the shared_ptr to A used to be located.

During the lifetime of the Unit, lots of pointers to this Unit is created at several different locations in my program.

Redesign the system to avoid that inconvenient circumstance.

I don't know what you're trying to do, but I suspect that there's really no good reason to keep all those pointers scattered around.

Do you have any PDF or websites that explains how to construct games without lots of pointers? I have trouble understanding how a trap could smash the goblin unless the trap has a pointer to the goblin, or how the quality of an item would be if not the workbench has a pointer to the crafter. Inevitably there will be much pointers to Units for all I know.

If you don't understand the stuff written here, please sharpen your C++ skills.

#6BitMaster  Members

Posted 24 September 2012 - 02:35 AM

A 'simple' solution would be add shared_ptr to the 'main vector' and weak_ptrs to the other vectors. When you try to access an element via the other vectors check if the weak pointer still holds an instance and remove it if it does not.

Of course, that is pretty ugly and fragile. The proper way would be deciding on proper ownership semantics and not storing the pointer all over the place.

#7patrrr  Members

Posted 24 September 2012 - 02:57 AM

Do you have any PDF or websites that explains how to construct games without lots of pointers? I have trouble understanding how a trap could smash the goblin unless the trap has a pointer to the goblin, or how the quality of an item would be if not the workbench has a pointer to the crafter. Inevitably there will be much pointers to Units for all I know.

Just an idea, when the trap gets updated, can't it ask the world for all goblins in the vicinity and then do smash-checking? The goblin is then notified that it is being smashed. Ie:

void Trap::update(double dt) {
Goblin &closestGoblin = world.getGoblin(myPosition);
if (distance(closestGoblin, *this) <= 10 && shouldBeSmashing)
closestGoblin.smash();
}


It's a bit like thinking the other way around, and it makes code more straight-forward.

Edited by patrrr, 24 September 2012 - 03:01 AM.

#8rip-off  Moderators

Posted 24 September 2012 - 03:00 AM

If I have a vector of shared_ptr whereas one of the shared_ptrs are pointing to object Foo, and Foo is deleted, does the vector erase the element with a shared_ptr to Foo? From what I understood this is not the case, and hence not a solution to my problem... Although it is very likely I have misunderstood the concept of shared_ptr. To me it seems that shared_ptr can be dangling aswell since the vector still has an element where the shared_ptr to A used to be located.

With shared_ptr<>, the object is only deleted when the last shared_ptr is itself destroyed. So if you remove a Goblin from the list of objects in the world, the Goblin is not yet deleted unless the trap is also destroyed. This is probably not what you want.
The other approach is to have a mixture of shared_ptr<> and weak_ptr<>. Weak pointer indicates knowledge of the existence of a given Goblin, but does not actually keep it alive. When you want to use a weak_ptr<>, you must first "lock" it, creating a shared_ptr<> while you do your work. You can also test if the weak_ptr<> still points to something. Provided that this shared_ptr<> is transient, this would allow for your Goblin / Trap scenario.

I have trouble understanding how a trap could smash the goblin unless the trap has a pointer to the goblin...

Presuming that the Trap is an area affect, I would design this so that the Trap creates some kind of notification callback inside the physics / collision code. When a Goblin, or any object, enters the area that the Trap has defined, the engine calls back into the trap, passing a (transient) pointer/reference to the game object. The trap can then apply damage to that object, and optionally remove itself from the callback code (if it is a one-use trap).

... or how the quality of an item would be if not the workbench has a pointer to the crafter.

Set the quality of an object only when it is actually created. You can have a collection of item prototypes on the workbench - it is only when a crafter uses the workbench that you create a fully item object with various statistics.

Inevitably there will be much pointers to Units for all I know.

The two approaches I mentioned above try to minimise this inter-object dependencies. Try to structure the game so that objects only know about each other briefly - just when they are in the middle of some interaction. One way to break the dependency is by using some kind of "world" object that provides an interface for querying the game world and game objects around each object.

Now, this doesn't always work. For instance, a homing fireball spell must have a persistent way to "remember" the actor it is chasing. One way to handle that is using a weak_ptr<> like above. Another is for the spell to store an object identifier, and for the spell to periodically query the world to determine the status of its victim. Finally you might have a callback system where the spell can register to "listen" to changes in the victim, such as them moving or dying.

#9Goran Milovanovic  Members

Posted 24 September 2012 - 03:27 AM

As BitMaster said: "The proper way would be deciding on proper ownership semantics and not storing the pointer all over the place.".

What patrrr did is fine (although, I think "smash" should be a method on the Trap, not the Goblin): You get the object when you need it, you do something to it, and then you let it go.

+---------------------------------------------------------------------+

| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+

#10stillLearning()  Members

Posted 24 September 2012 - 07:20 AM

Thanks for all the great replies!

I will definitely reconsider ownership. Although in some cases its not possible to live without vectors of pointers. I have maybe been unclear in my question or I simply fail to understand how your suggestions would solve my problem. For example my unit class has a member:
//Forward declaration
class Renderable;

class Unit
{
...
Renderable *renderable;
...
};


The class Renderable has a static pointer to class Renderer.

In Renderable constructor (which is called once a Unit is created..)

Renderable::Renderable(...)
{
renderable->SendRenderableToRenderer();
}


To summarize: When an Unit is created, its component Renderable sends a pointer of itself to Renderer. Renderer has a vector renderableEntities

vector<Renderable*> renderableEntities;


which iterates every gameloop and renders images if needed. If the Unit is deleted its component Renderable is deleted, but the class Renderer now has a dangling pointer in renderableEntities. This can be fixed by always letting Renderable knowing in which vectors it exists in by having a pointer to the renderableEntities vector... In ~Renderable()

ptrToRenderableEntities->erase(index where this == adress of element).

If this is not done renderableEntities will expand by 1 element everytime a Renderable is created and deallocated. Can someone explain why using weak_ptr or shared_ptr could replace my Send & Forget-system? I am sorry if it seems like Im not listening, trust me I am, I just cannot understand why boost would solve this problem since boost doesnt autoerase dangling pointers from vectors. I know using vectors with pointers is generally a bad practice, but in my Rendering system I cant find any other solution.

(Also Im at a hurry right now, I will clarify when I come home from work if needed!)

If you don't understand the stuff written here, please sharpen your C++ skills.

#11patrrr  Members

Posted 24 September 2012 - 07:34 AM

...
which iterates every gameloop and renders images if needed. If the Unit is deleted its component Renderable is deleted, but the class Renderer now has a dangling pointer in renderableEntities. This can be fixed by always letting Renderable knowing in which vectors it exists in by having a pointer to the renderableEntities vector... In ~Renderable()
...

Just be careful not to remove a Renderable while you're iterating over the renderableEntities vector.

#123DModelerMan  Members

Posted 24 September 2012 - 09:25 AM

I use a reference counting system. It's a simple ReferenceCounted interface with grab() and release() methods. If you want to see a good implementation look at Irrlicht's. The difference though is that I wrote a RefHandle template. I use it to replace pointers. All it does is grab()s the object in it's constructor, and release()s it in it's destructor (there's some code for copying too, but that's the basic idea). It works great and keeps messy pointer management out of the way.

#13Goran Milovanovic  Members

Posted 24 September 2012 - 01:36 PM

To summarize: When an Unit is created, its component Renderable sends a pointer of itself to Renderer. Renderer has a vector renderableEntities

The Renderer should not contain a vector of renderable entities. Instead, you should get the renderable when needed, by iterating over the global units container:

for (int i = 0; i < units.size(); ++i){
renderer.drawRenderable(units[i].getRenderable());
}


+---------------------------------------------------------------------+

| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+

#14stillLearning()  Members

Posted 25 September 2012 - 12:16 AM

To summarize: When an Unit is created, its component Renderable sends a pointer of itself to Renderer. Renderer has a vector renderableEntities

The Renderer should not contain a vector of renderable entities. Instead, you should get the renderable when needed, by iterating over the global units container:

for (int i = 0; i < units.size(); ++i){
renderer.drawRenderable(units[i].getRenderable());
}


Thanks Goran! It really makes more sence now that I think of it. As you might notice Im still getting the hang of OOP and general program architecture, but I must say that this thread has given me alot of nice pushes in the right direction and also concrete tips which I appreciate a lot.

Offtopic: This community is great.

If you don't understand the stuff written here, please sharpen your C++ skills.

#153DModelerMan  Members

Posted 25 September 2012 - 09:04 AM

By the way: you can use the reference counting class that I wrote if you want to.

[source lang="cpp"]#ifndef I_REFERENCE_COUNTED_H#define I_REFERENCE_COUNTED_H///@brief The IReferenceCounted interface is used for reference counted memory management. It is recommended to use the RefHandle class///with IReferenceCounted instead of pointers.///@brief TODO: implement ref counting as atomic operations.class IReferenceCounted{public: IReferenceCounted() :m_refCount(0) {} virtual ~IReferenceCounted(){} ///@brief Returns the current reference count. const unsigned int getReferenceCount(){return m_refCount;} ///@brief Adds one reference. void retain() const { m_refCount++; } ///@brief Subtracts one from the reference counter, and deletes the object if refcount drops to 0. void release() const { m_refCount--; if ( m_refCount <= 0 ) delete this; } ///@brief Resets the reference counter to 0 without deleting the object (used to clone objects) void reset() { m_refCount = 0; }protected: mutable int m_refCount;};///@brief RefHandle provides a smart pointer for reference counted objects only use this handle with classes derived from IReferenceCountedtemplate<typename T>class RefHandle{public: RefHandle() :m_obj(NULL) {} RefHandle(const RefHandle& oth) { m_obj = oth.m_obj; if ( m_obj ) m_obj->retain(); } RefHandle(T* obj) :m_obj(obj) { if ( m_obj ) m_obj->retain(); } ~RefHandle() { if ( m_obj ) m_obj->release(); } ///@brief Releases the current object and sets the pointer to a different object. ///Passing NULL or 0 will release the object and won't add a new one. void reset(T* obj) { if ( m_obj ) m_obj->release(); m_obj = obj; if ( m_obj ) m_obj->retain(); } ///@return False if the handle points to no object. True if the handle points to a valid object. bool isValid() { return m_obj != NULL; } ///@brief Assigns a pointer to this object, equivalent to calling RefHandle::reset(T* obj) RefHandle& operator = (T* obj){reset(obj); return *this;} ///@return The actual pointer. T* get(){return m_obj;} T* operator->() const {return m_obj;} T& operator*() const {return *(get());} ///@brief Allows regular pointers to be assigned to from a RefHandle operator T*() const {return m_obj;} ///@brief Allows RefHandle instances to be checked for validity. Equivalent to if ( ptr.isValid() ) operator bool() const {return m_obj!=NULL;} bool operator==(const RefHandle& handle) {return handle.m_obj == m_obj;} bool operator==(const T* obj) {return obj == m_obj;}private: T* m_obj;};#endif[/source]

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.