What solutions are there for circular references?

I've looked at the problem a dozen different ways over the years, and the only solution I've found that works every time is to re-architect my solution to not use a circular reference.

Edit:

Can you expand? For example, how would you deal with a parent-child relation when the child needs to know about/access the parent? – OB OB

As I said, the only good solution is to avoid such constructs unless you are using a runtime that can deal with them safely.

That said, if you must have a tree / parent-child data structure where the child knows about the parent, you're going to have to implement your own, manually called teardown sequence (i.e. external to any destructors you might implement) that starts at the root (or at the branch you want to prune) and does a depth-first search of the tree to remove references from the leaves.

It gets complex and cumbersome, so IMO the only solution is to avoid it entirely.

+1 same here. For a sample approach see my answer on another question: stackoverflow.com/questions/1047877/…

Can you expand? For example, how would you deal with a parent-child relation when the child needs to know about/access the parent?

@ChrisW: Weak references were mentioned in the original question. OB OB was looking for alternatives.

Here is a solution I've seen:

Add a method to each object to tell it to release its references to the other objects, say call it Teardown() .

Then you have to know who 'owns' each object, and the owner of an object must call Teardown() on it when they're done with it.

If there is a circular reference, say A B , and C owns A , then when C 's Teardown() is called, it calls A 's Teardown() , which calls Teardown() on B , B then releases its reference to A , A then releases its reference to B (destroying B ), and then C releases its reference to A (destroying A ).

I think that in most cases, you'd like to call teardown from within the object's destructor. Calling teardown explicitly is somewhat similiar to destroying the object manually. (How do you know that nobody else is using the object when tearing it down?)

Yes, you're right, call Teardown in the object's destructor. However, calling Teardown doesn't necessarily destroy the object, if someone else has a reference to it then it will stay alive. Objects only get destroyed when reference counts reach 0.

Let me correct that: Calling Teardown on an object does not necessarily destroy it, but it means the object is not longer useful, its similar to calling Dispose(). Since the object has released its references to the objects it depends on, its not safe to use.

@Alex Black: What if there are 2 objects C and D who own A. Then when C calls Teardown(), but D still wants it alive ? You have to have a counter in object A that will ignore all Teardown calls except last one.

@alpav: What we did was avoided that scenario. Only one of C or D could own A. Say C owns A and D does not, but D has a reference to A, then you have to design your code in such a way that D doesn't access A after C is gone, one way to do that is make D owned by C.

I guess another method, used by garbage collectors, is "mark and sweep":

1. Set a flag in every object instance
2. Traverse the graph of every instance that's reachable, clearing that flag
3. Every remaining instance which still has the flag set is unreachable, even if some of those instances have circular references to each other.

As i said, I am not asking for alternatives to refernce counting, but for solutions to circular references.

What's the "problem" with circular references that you're trying to solve: is it the problem of garbage collection, or a different problem? If the problem is garbage collection, isn't an alternative the same thing as a solution?

@ChrisW: Yes, the problem is generally garbage collection. There are many methods for garbage collections. One of them is reference counting, another one is mark-and-sweep. Mark-and-sweep is an example of an alternative to reference counting as a gc method, weak-references are an example to a solution to circular references while still using reference counting as the gc method, on the other hand. I hope you see the difference.

If you want to do it using only first-class references, then you need a way to detect circularity. Alex Black's method should do that: pretend to deference everything that a referenced object is pointing to, and if that experiment results in the original object's being dereferenced then it's a circular reference. I don't know but maybe that's an expensive way to do it: more expensive than mark and sweep, especially in pathological / long-chain cases.

You could actually use a garbage collector in tandem with reference counting. The reference count causes stuff to be cleaned up immediately if possible, and the GC handles the circular references (and if MOST things are automatically deleted via the reference count, the GC has less work to do!)

I'd like to suggest a slightly different method that occured to me, I don't know if it has any official name:

Objects by themeselves don't have a reference counter. Instead, groups of one or more objects have a single reference counter for the entire group, which defines the lifetime of all the objects in the group.

In a similiar fashion, references share groups with objects, or belong to a null group.

A reference to an object affects the reference count of the (object's) group only if it's (the reference) external to the group.

If two objects form a circular reference, they should be made a part of the same group. If two groups create a circular reference, they should be united into a single group.

Bigger groups allow more reference-freedom, but objects of the group have more potential of staying alive while not needed.

That's equivalent to stating which of your references are 'weak': if a reference is to an object in the same group then the reference is 'weak', else it's to an object in a different group and so that reference is 'strong'.

Yeah, only that if you have an external reference to object A that holds the weak reference to object B, and B is not otherwise referenced, B would still stay alive (which is the wanted behavior). You don't get that with "ordinary" weak references.

Sounds similar to having discreet memory pools for different parts of the application (so you can just delete an entire pool at once and then its just cleaning up pointers into the pool), which is commonly used in games, and adding a reference count (which i guess would solve the problem of cleaning up pointers)

Put things into a hierarchy

Having weak references is one solution. The only other solution I know of is to avoid circular owning references all together. If you have shared pointers to objects, then this means semantically that you own that object in a shared manner. If you use shared pointers only in this way, then you can hardly get cyclic references. It does not occur very often that objects own each other in a cyclic manner, instead objects are usually connected through a hierarchical tree-like structure. This is the case I'll describe next.

Dealing with trees

If you have a tree with objects having a parent-child relationship, then the child does not need an owning reference to its parent, since the parent will outlive the child anyways. Hence a non-owning raw back pointer will do. This also applies to elements pointing to a container in which they are situated. The container should, if possible, use unique pointers or values instead of shared pointers anyways, if possible.

Emulating garbage collection

If you have a bunch of objects that can wildly point to each other and you want to clean up as soon as some objects are not reachable, then you might want to build a container for them and an array of root references in order to do garbage collection manually.

Use unique pointers, raw pointers and values

In the real world I have found that the actual use cases of shared pointers are very limited and they should be avoided in favor of unique pointers, raw pointers, or -- even better -- just value types. Shared pointers are usually used when you have multiple references pointing to a shared variable. Sharing causes friction and contention and should be avoided in the first place, if possible. Unique pointers and non-owning raw pointers and/or values are much easier to reason about. However, sometimes shared pointers are needed. Shared pointers are also used in order to extend the lifetime of an object. This does usually not lead to cyclic references.

Bottom line

Use shared pointers sparingly. Prefer unique pointers and non-owning raw pointers or plain values. Shared pointers indicate shared ownership. Use them in this way. Order your objects in a hierarchy. Child objects or objects on the same level in a hierarchy should not use owning shared references to each other or to their parent, but they should use non-owning raw pointers instead.