How to detect cycles when using shared_ptr

Question

shared_ptr is a reference counting smart pointer in the Boost library.

The problem with reference counting is that it cannot dispose of cycles. I am wondering how one would go about solving this in C++.

Please no suggestions like: "don't make cycles", or "use a weak_ptr".

Edit

I don't like suggestions that say to just use a weak_ptr because obviously if you know you will create a cycle, then you wouldn't have a problem. You also cannot know you will have a cycle in compile time if you generate shared_ptrs during runtime.

So please, self delete answers that use weak_ptr in them because I specifically asked not to have those kind of answers...

Answer 1

It's fairly easy to detect cycles:

• set a count to some largish number, say 1000 (exact size depends on your application)
• start with the pionter you are interested in and follow pointers from it
• for each pointer you follow, decrement the count
• if the count drops to zero before you reach the end of the pointer chain, you have a cycle

It's not, however, very useful. And it is not generally possible to solve the cycvle problem for ref-counted pointers - that's why alternative garbage colection schemes like generation scavenging were invented.

Answer 2

I haven't found a much better method than drawing large UML graphs and looking out for cycles.

To debug, I use an instance counter going to the registry, like this:

template <DWORD id>
class CDbgInstCount
{
public:
#ifdef _DEBUG
   CDbgInstCount()   { reghelper.Add(id, 1); }
   CDbgInstCount(CDbgInstCount const &) {  reghelper.Add(id, 1); }
   ~CDbgInstCount()  { reghelper.Add(id, -1); }
#else
#endif
};

I just ned to add that to the classes in question, and have a look at the registry.

(The ID, if given as e.g. 'XYZ!' will be converted to a string. Unfortunately, you can't specify a string constant as template parameter)

Answer 3

A combination of boost::weak_ptr and boost::shared_ptr maybe? This article may be of interest.

Answer 4

shared_ptr represents ownership relation. While weak_ptr represents awareness. Having several objects owning each other means you have problems with architecture, which is solved by changing one or more own's into aware of's (that is, weak_ptr's).

I don't get why suggesting weak_ptr is considered useless.

Answer 5

I know you said "no weak_ptr" but why not? Having your head with a weak_ptr to tail, and tail with a weak_ptr to head will prevent the cycle.

Answer 6

See this post on detecting cycles in a graph.

Answer 7

The generic solution to finding a cycle can be found here:

http://stackoverflow.com/questions/34249/best-algorithm-to-test-if-a-linked-list-has-a-cycle

This assumes that you know the structure of the objects in the list, and can follow all of the pointers contained in each object.

Answer 8

I understand your annoyance at being glibly told to use weak_ptr to break cyclic references and myself I almost feel rage when I am told that cyclic references are bad programming style.

Your ask specifically how do you spot cyclic references. The truth is that in a complex project some reference cycles are indirect and difficult to spot.

The answer is that you should not make false declarations that leave you vulnerable to cyclic references. I am serious and I am criticizing a very popular practice - blindly using shared_ptr for everything.

You should be clear in your design which pointers are owners and which are observers.

For owners use shared_ptr

For observers use weak_ptr - all of them, not just those you think may be part of a cycle.

If you follow this practice then the cyclic references will not cause any problems and you don't need to worry about them. Of course you will have a lot of code to write to convert all these weak_ptrs to shared_ptrs when you want to use them - Boost really isn't up to the job.