Hi there, recently I encounter a problem about circularly linked objects. Following are two classes declared in my small engine. Node is basically a hierarchical representation of transformation, and Entity is object in the game scene. Every Entity must have a node, each node can have several child nodes. What I want to do is deleting either of entity or node will delete both of them, and also deleting a node will somehow notify its parent. Could anyone help with this? or is there a better structure to organize relationship between hierarchical transformation and game object? Thanks in advance.

Class Entity
{
   ~Entity()
   {}

   Node *m_node;
}

Class Node
{
   ~Node()
   {}
   Node *m_parent;
   vector<Node *> m_children;
   Entity *m_entity;
}

1.) Don't use the delete operator. Make the d'tor protected and provide and explicit destruction:

// deletes any dependents
void Node::destruct();

Notice that this way includes the invoked element to know about destruction automatically.

The routine can also be written to delete the own object as last task if you want to.

2.) Deleting the full hierarchy regardless at which point you tackle is IMHO not good. If the whole hierarchy is ever the target, then make the top element destructible and all child elements allow to get a pointer to the top element. E.g. one of

myNode->entity()->destructAll();

IMHO:

* A Node should be destructible but not deletable with the exception of friend classes;

* destruction should be strictly top done and only for child nodes;

* the Entity could be deletable.

Thank you for your reply but I'm not sure what you mean by destructible. If I destruct a node, I delete whatever m_entity points to and set m_parent and m_entity to null, is this what you mean?

Are the references actually circular or are you just talking about a node which may belong to multiple entities? To handle the latter you can use a std::shared_ptr wrapper for your node objects. It will automatically count the number of references to the node and call the delete operator when the object containing the last reference is deleted.

Dealing with circular references is much harder. Some approaches are to use weak pointers (std::weak_ptr) to allow an object to know about another without having ownership (i.e. holding the weak reference will not prevent the object from being deleted). If you can't design the solution in this way, there are more elaborate methods where you scan your objects, detect the circular reference and delete objects which are unreachable in the graph. But it's normally much simpler to just not use (strong) circular references at all.

Thank you for your reply but I'm not sure what you mean by destructible. If I destruct a node, I delete whatever m_entity points to and set m_parent and m_entity to null, is this what you mean?

Something like:

class Node {

friend class Entity;

protected: // <<< Node is protected from being deleted or destructed if not called from either Node or Entity

    ~Node();

    void destruct();
};

Node::~Node() {
    destruct();
}

void Node::destruct() {
    // iterating m_children and deleting them here
}


class Entity {

public: // <<< at top level things are public

    ~Entity();

    void destruct();

};

Entity::~Entity() {
    destruct();
}

void Entity::destruct() {
     delete m_node;
}

When a parent is deleting a child, the first thing it does is set the child's parent pointer to null (ie; it detaches it from the tree) and then it deletes it. That breaks the cycle. The parent doesn't need to be told the node is going away, because it already knows -- it's doing it.

Now the child's destructor can say "if (parent) parent->i_am_being_deleted(this);" so if someone else deletes it, the parent can remove it from the child list.

I am not quite sure what you mean by circular referencing in your very case. You have only parent and childs pointers in your node class. Do you mean a child can be parent of its parent?

In this case of referencing, when you delete a node that has childs, and you wish to delete whole subtree, you do not do it tree way, but a graph way. Tree is a certain typpe of graph, and circular dependency does not exist in trees. Consider graph A-B-C-A, and graph A-B-C-B . You are removing node B in case of graph two. That means you will remove node C as well. In case of graph one, you wish to remove node C, which will result in removing node A-B, entire graph.

But! Very important thing to know about not tree graphs is that hierarchy cannot be implemented to them. In your case of hiearchy, meaning you do not wish invalidated pointers access, you would remove the circle the node is part of. COnsider graph

A-B-C-D-E-F-D-A , two circles, removing a circle containing delted node will leave you with nodes that are valid.

I am not quite sure what you mean by circular referencing in your very case. You have only parent and childs pointers in your node class. Do you mean a child can be parent of its parent?

No, but thank you for your time. I mean Entity has pointer to Node, Node also has pointer to Entity. When you call destructor on Entity, it would call Node's destructor, Node's destructor would in turn call Entity's destructor, which is kinda "circular".

(1) Node is basically a hierarchical representation of transformation, and Entity is object in the game scene. Every Entity must have a node, each node can have several child nodes.

What I want to do is

(2) deleting either of entity or node will delete both of them, and also

(3) deleting a node will somehow notify its parent.

Circular ownership references are troublesome. It's best to avoid them alltogether.

(1) Sounds like Node as such has no right to exist, but several Entity objects may own the same node ---> use a shared_ptr<Node> in Entity. This gives a many-to-one relationship, and when the last Entity having a hold on a Node is destroyed, the now useless Node goes away, too. No need to do anything special.

(2) This is hard, if possible at all, and not easy to do in an easy, clean, unambiguous way. It is however also someting you likely don't need to (or don't want to) do either. Do you really need to delete entities by deleting nodes? Really? If that is so, find all the entities in the node by the back-pointer, remove them from whatever container owns all entities (so they're not double-deleted) and delete them. Don't touch the Node, the shared_ptr will take care of that, once it is not needed any more.

(3) This becomes somewhat obsolete, since there are no entities owning a node left when it's deleted (and otherwise, it is not valid to do so! It would leave orphaned entities around). But if you still want to achieve that, invoke a callback on each entity pointer from Node's destructor.