Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This Stack Overflow question is about a child having reference to its parent, through a pointer.

Comments were pretty critical initially of the design being a horrible idea.

I understand this is probably not the best idea in general. From a general rule of thumb it seems fair to say, "don't do this!"

However, I am wondering what sorts of conditions would exist where you would need to do something like this. This question here and associated answers/commentary suggests even for graphs to not do something like this.

share|improve this question
1  
The question you linked seems pretty comprehensive on the subject. – Lightness Races in Orbit Jan 4 at 21:45
4  
@LightnessRacesinOrbit "don't do this" isn't really useful as far as understanding why. – enderland Jan 4 at 21:46
2  
I see a lot more than "don't do this" there. I see pros and cons debated by multiple experts. – Lightness Races in Orbit Jan 4 at 21:57
1  
You may have a bi-directional list that needs traversing, some kind of circular buffer, perhaps you are representing two pieces of connected road in a game - if you need to represent something circular, then this may be a good idea. – rhughes Jan 5 at 3:03
1  
My pragmatic rule of a thumb is a question "Can a Child exist without a Parent?". (If you consider XmlDocuments and its nodes: a node cannot exist without a document's tree context. It's a nonsense). If the answer is no then bi-directional links are all right: you have two objects which can exist only together. If objects can exist independently, then I remove one of those two links. – mikalai Jan 8 at 20:27
up vote 36 down vote accepted

The key here is not whether two objects have circular references, but whether those references indicate ownership of each other.

Two objects cannot "own" each other: this causes an intractable dilemma for initialization and deletion order. One must be an optional reference, or otherwise indicate that one object will not manage the other's lifetime.

Consider a doubly-linked list: two nodes link back and forth to each other, but neither "owns" the other (the list owns them both). This means neither node allocates memory for the other or is otherwise responsible for the identity or lifetime management of the other.

Trees have a similar relationship, although nodes in a tree may allocate children and parents do own children. The link from a child to parent helps with traversal, but again does not define ownership.

In most OO designs, a reference to another object as an object's data member implies ownership. For example, suppose we have classes Car and Engine. Neither one is very useful on its own. We can say that these objects depend on each other: they require the presence of the other in order to perform useful work. But which "owns" the other? In this case we would say that Car owns Engine because the car is the "container" in which all of the automotive components live. In both an OO and real-world design, the car is the sum of its parts, and all of those parts are connected together within the context of the car. Engine may have a reference back to Car, or it may have a reference to TorqueConverter, but no component inside of Car owns Car even if said component has a reference to the Car.

Circular references can be a bad design smell, but not necessarily. When used judiciously and documented correctly, they can make using data structures easier.

Try traversing a tree without references going both ways between parents and children. Sure, you could come up with a stack-based approach that is brittle and complex, or you could use the reference-based approach that is trivially simple.

share|improve this answer

There are several aspects to consider in such a design:

  • the structural dependencies
  • the ownership relation (i.e.composition vs. other kind of associaton)
  • the navigation needs

Structural dependency between classes:

If you aim at reusing component classes, you should avoid unnecessary dependency and avoid such closed circular structures.

Nevertheless sometimes two classes are conceptually strongly interlinked. In this case, avoiding dependency is not a real option. Example: a tree and its leafes, or more generally a composite and its components.

Ownership of objects:

Does one object owns the other ? Or otherwise stated: if one object is destroyed, shall the other be destroyed as well ?

THis topic was addressed in depth by Snowman, so I'll not going to address it here.

Navigation needs between objects:

A last issue is navigation need. Let's take my favourite example, the composite design pattern of the Gang of four.

Gamma & al. explictely mention the potential need to have an explicit parent reference: "Maintaining reference from child componenents to their parent can simplify traversal and management of a composite structure" Of course you could imagine a systematic top-down traversal, but for very large composite objects it can significantly slow down the operations and in an exponential manner. A direct reference, even circular can significantly ease manipulation of your composites.

An example could be a graphical model of an electronic system. A composite structure could represent the electronic boards, circuits, elements. To display and manipulate the model, you'd need some geometrical proxies in a GUI view. It is then certainly much easier to navigate from the GUI element selected by the user to the component, to find out which is the parent and with are the related brother/sister elements, than to start a top down search.

Of course, as Gamma & al pointed out, you have to ensure the invarients of the circular relationship. This can be tricky, as the SO question you refer to has shown. But it's perfectly manageable and in a safe manner.

Conclusion

The navigation need shall not be understimated. It is not without reason that UML has explicitely adressed it in the modelling notation. And yes, there are perfectly valid situation where circular references are needed.

The only point is that sometimes people tend to go into such a direction to quickly. So it's worth to consider all the 3 aspects involved before taking the decision to go for it or not.

share|improve this answer
1  
This answer is IMHO heavily undervoted. The OP asked: "Given there is already a parent-child relationship, when is it ok to implement this by a circular reference". So the structure and the "ownership" (in the sense mentioned here) is already clear. That means the only criteria for adding references on one side or the other are the questionsof "navigational needs" and "independent reusage of the child". – Doc Brown Jan 5 at 13:31
    
@DocBrown - You could always put a bounty on this question once it becomes eligible. :-) – GlenH7 Jan 5 at 20:40
1  
@GlenH7: that would not give this answer more votes, only Snowman's answer (for which I think it misses somewhat the point of the question). – Doc Brown Jan 5 at 21:52
1  
@DocBrown - But the repz, man, the repz! – GlenH7 Jan 5 at 21:52
    
...and if you add visibility choices like public-private-protected, that gives you 9 different options :) – mikalai Jan 8 at 20:31

Usually, circular references are a very bad idea because they mean circular dependencies. You probably already know why circular depedencies are bad, but for completeness' sake, the tl;dr version is that whenever classes A and B both depend on each other, it's impossible to understand/fix/optimize/etc either A or B without also understanding/fixing/optimizing/etc the other class at the same time. Which quickly leads to codebases where you can't change anything without changing everything.

However, it is possible to have a circular reference without creating evil circular dependencies. This works as long as the reference is strictly optional in a functional sense. By that I mean you could easily remove it from the classes and they would still work, even if they happen to work slower. The main use case I'm aware of for such circular non-dependency-creating references is enabling quick traversal of node-based data structures such as linked lists, trees and heaps. For instance, in principle any operation you can perform on a doubly-linked list you can also perform on a singly-linked list, there just happen to be a few operations (like moving backwards through the list) that have a much better big-O with the doubly-linked version.

share|improve this answer

The reason it's usually not a good idea to do this is because it violates the Dependency Inversion Principle. People have written a lot about this in much more detail than I can cover adequately in this post, but it boils down to making it difficult to maintain, because the coupling is so tight. Changing either class almost always necessitates a change in the other, whereas if the dependencies only point one way, changes on one side of the interface are isolated. If both classes point to an abstract interface, even better.

The one main exception is when you don't have two different classes at different abstraction levels, but two nodes of the same class, such as in a tree, a doubly-linked list, etc. Here it's more of a structural relationship than an abstraction relationship. Circular references for the sake of algorithmic efficiency are acceptable and even encouraged in these sorts of cases.

share|improve this answer

[...] suggests even for graphs to not do something like this.

Data Structure POV

This is just going to be a variety answer from the data structure standpoint rather than a comprehensive one, but I've created some data structures for which I couldn't find any way to avoid the raw pointer back from child to parent. That might have just been a defect in the way I was approaching it. As a caveat, I'm assuming "pointer" here means "raw pointer" which implies to me that the child is simply "referencing" the parent but not owning it (circular ownership would be a huge problem, especially in C++ if you used like a shared_ptr in A to B which stores a shared_ptr back to A -- this would end up just leaking memory since there's no protection against cycles like this there).

I ended up using such a data structure as the heart of this program: https://www.lightwave3d.com/chronosculpt/ -- a little teeny software I wrote (not my proudest moment as I had to code the whole thing with the exception of interchange support and licensing on my own, and in a matter of months -- also my last work at a company setting since I got fed up with that kind of environment).

The problem is that I needed to deal with meshes which were animating and being sculpted interactively with millions of polygons (sometimes with every single vertex moving at every single frame) at acceptable frame rates, while also providing reasonably-fast spatial searches for things like picking, sculpting, and collision.

Normal spatial indexing structures like bounding volume hierarchies are often what we use, and I tried to use a variety of these including a loose-fitting one with expanding bounding boxes. Yet it was too difficult to meet those 30+ FPS demands on like an i3 when I had a 7 million triangle mesh of a creature running to update this data structure every single frame with all these vertices moving around.

These data structures tend to be ideal for static content that's not deforming every frame, or at least not dynamic content of this sort that spans in the millions of vertices. Intel's BVH was considered to be really great for being able to handle deformations of meshes with 30k polygons at over 30 frames per second in a raytracer context, but I was looking at a need for millions of polygons at such a frame rate in an OGL context (not as critical for searching as a raytracer, but needed dramatically faster updates of the acceleration structure in response to deformation).

Bottom-Up Traversal

So the data structure I designed was not based on spatial partitioning. I probably can't give too away too many details for IP reasons, but the key to rapid updates was based on the stability of the hierarchical structure. It didn't need to split nodes apart or rebalance the tree or anything like that. All it needed was to update bounding boxes bottom-up, starting from a list of modified vertices and working upwards and updating bounding boxes to the root.

That was the key to getting the necessary frame rates, and the bottom-up access pattern made it so I couldn't really see a way to avoid the back pointer. I tried initially to avoid it and mark all the leaf nodes as "dirty" first, then traverse the tree from top-down looking for dirty leaf nodes, but I couldn't get the desired performance that way working top-down instead of bottom-up for localized edits to mesh (sculpting, e.g.). It ended up being cheaper to just store some state with these nodes (they were "fatter nodes" for an n-ary tree) so that fewer nodes would need to be accessed working bottom-up from the vertices that were moved and propagating updates up the tree.

Maybe I did something wrong. I just couldn't find a way around it. It was in a rush setting so maybe I just didn't take the time to properly think through and come up with a new data structure that avoids the problem. I've been thinking about this for a while since this question was raised though and I still can't come up with a way to avoid the back pointer, so maybe that's one legit case to do this (unless I have a huge blind spot, which is very possible).

Simplified diagram of the idea (though actual one was n-ary):

enter image description here

Wasteful Back Pointers

I've seen some data structures published where back pointers were used by the authors just for convenience, like with a tree that is always traversed top-down but then works its way back up from leaf to root. The developers were too lazy to construct a stack or recursively pass a parameter, so they just used a back pointer as a kind of convenience. There I can see how it can be really bad, especially when publishing a paper on such an algorithm and then using the back pointer when it could easily be avoided.

In those cases the back pointer seems wasteful, and possibly even more error-prone (more persistent, avoidable state can make things harder to manage).

I'm hoping my example doesn't fit in that category, since I think mine really absolutely needs the bottom-up traversal. In my case, the list of leaf nodes to affect wasn't always obtained starting with a top-down tree traversal. It was sometimes obtained through other data structures, like the mesh data structure traversal itself. This was the main reason I felt I couldn't avoid the back pointer even though they're usually quite wasteful.

share|improve this answer
1  
Yes, this example is really appropriate. Exactly the kind of things I was trying to describe in my argument about navigation in a composite: the backpointer accelerates considerably the speed. Thanks for your interesting performance anecdote and very clear diagram ! +1 – Christophe Jan 5 at 22:10
    
@Christophe I like your example as well! I wasn't sure if I was actually answering the question properly since perhaps it was more about "circular ownership" than just back pointers that let us get traverse a data structure upwards/backwards. But I was mainly responding to that last "graph" part of the question. – Ike Jan 5 at 22:30

Doom 3 has an example of a child object with a pointer to a parent object. Specifically it uses intrusive lists. To summarize, an intrusive list is like a linked list except each node contains a pointer to the list itself.

Advantages:

  • When objects can exist in several lists simultaneously, the memory for the list nodes needs to be allocated and deallocated only once.

  • When a object needs to be destroyed, you can easily remove it from all of the lists it's in without searching through each list linearly.

I think this is a pretty specific scenario, but if I understand your question, it's an example of an acceptable use of a child object containing a pointer to its parent object.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.