reference counting with cycles in C++ smart pointer

In shared_ptr smart pointer, reference counting is used. However, reference counting has a problem, that it can't break cycles of reference.

I have four questions with this issue.

1) Could anybody offer me one snippet in which the cycles of reference happened?

2) If it can't break cycles of reference, how does RCSP guarantee success resource manage? Is there any way to break the cycles with 3rd party product?

3) Is there anyway to avoid the cycles of reference?

4) How about other smart pointers? How does they deal with the source manage? For example, share_ptr, scope_ptr?

Many thanks!

Answers


The usual way to avoid cycles is to use weak references in any one point of the cycle. shared_ptr has a companion type, weak_ptr, which is designed for this purpose.

Which part of the cycle to weaken is a matter of design. In designs where "parent" objects own "children", then the reference from parent to child should be strong (shared_ptr), and the reference from child back to parent should be weak (weak_ptr).


Practical uses that involve cycles are quite a few kinds of graphs. A trivial snippet (though one that's unlikely to happen in real life) would be something like:

struct node {
    node *next;
};

int create_cycle() {
    node *a = new node;
    a.next = a;
}

After create_cycle returns, the node we just allocated contains a reference to itself, but there's no other point to it, so a reference counter won't collect it even though it's garbage.

Chris Jester-Young has already dealt with cycle breaking with smart pointers from a practical viewpoint. He didn't go into any real detail about how it works internally though.

A weak_ptr is sort of a doubly-indirect pointer. I.e. the weak_ptr doesn't give acces directly with an object. Instead, to get to the object, you have to convert the weak_ptr to a shared_ptr, then use that to get to the object -- but the attempt to convert the weak_ptr to a shared_ptr will only succeed if there's still at least one other shared_ptr to the managed object (so the object has a nonzero reference count and still exists).

As such, a weak_ptr gives you access to an object as long as it exists, but "knows" when the object ceases to exist and doesn't give you access to the (now freed) memory where the object used to be if the object has been destroyed.

Avoiding cycles depends on the sorts of things you're working with. If you deal with graphs a lot (for one example) they're often almost impossible to avoid, simply because quite a few things you model have cycles. Otherwise, well...it depends. I'd guess a fair number of developers have gone for entire careers without ever having to create a linked structure that contains a cycle. Others probably do it several times in an average week.

As far as other smart pointers go, as noted above the weak_ptr type works in conjunction with the shared_ptr; you can use shared_ptr without ever using a weak_ptr, but to make much real use of a weak_ptr at some point you have to convert it to a shared_ptr.


Need Your Help

When would Visual Studio for Mac OS X /Objective C finally released as announced by Steve Ballmer?

iphone objective-c visual-studio osx

As I read here http://www.sdtimes.com/MAC_DEVELOPERS_EMBRACE_NET_WITH_VISUAL_OBJECTIVE_C/By_I_B__Phoolen/34234

Link against symlink instead of soname

linux elf dynamic-linking

I have an linux application, which on the linker line links against:

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.