views:

1752

answers:

7

In other words, how does the implementation keeps track of the count?

Is there a map-like object maintained which is accessible by all the shared_ptr instances whose key is the pointer's address and value is the number of references? If I've to implement a shared_ptr, this is the first idea that's coming to my mind.

Is there a possibility for a memory leak in case of these reference-counting smart pointers? If so, how can I avoid them?

+2  A: 

Assuming you are asking about Boost's shared_pointer, you can always answer these sorts of questions by looking at the source code.

anon
+1, even if boost::shared_ptr is not something simple to look at. Support for weak_ptr makes the code not-so-simple, and the code is divided in a set of public/private classes (implementation details). It is a good example of design nonetheless.
David Rodríguez - dribeas
@Neil, I did look at it before posting here but I was finding it really difficult to follow. Perhaps, I can look at the code a few weeks later after knowing more about C++ in general.
artknish
+1  A: 

No. shared_ptr just keep one additional pointer for reference counting.

When you make copy of shared_ptr object it copy pointer with count of references, increase it, and copy pointer on contained object.

bb
A: 

Creating a memory leak with reference-counting smart pointers is very easy. Just create any graph-like structure of objects that has a cycle in the graph. The objects in the cycle will prevent each other from being released. This can't be resolved automatically - for example, when you create a double-link list you have to take care of never removing more than one object at a time.

sharptooth
+2  A: 

Each smart pointer object contains a shared reference count - one for every raw pointer.

You could take a look at this article. This implementation stores these in a separate object which is copied around. You could also take a look at boost's documentation.

Search google for "C++ smart pointer implementation" or something similar for more details or take a look at the Wikipedia article on smart pointers.

Dan
-1. All smart pointers that refer to the same object must *share* a single reference count. The object holding the reference count is allocated by the first smart pointer object, and *pointers to it* (NOT the object itself) are copied when the smart pointer is copied.
j_random_hacker
Agree at j_random_hacker. The count is unique for each raw pointer and shared by all shared_ptr that refer to the same raw pointer. Usually it is allocated as a separate chunk of memory so smart_ptr hold two internal ptrs, one for the reference count and another for the pointer itself.
David Rodríguez - dribeas
-1 for static variable. Unless you are implementing a reference-counted smart pointer to a singleton object, you can't use statics to implement the reference counting.
John Dibling
I guess I messed up my wording, I MEANT that each pointer has a reference count and that each smart pointer references it. Fixed it (I hope)
Dan
I think perhaps Ferruccio's answer would make a better accepted answer
Dan
@Dan: I changed the answer and accepted Ferruccio's. The link did help me understand about smart pointers better. Thanks!
artknish
@Dan: Good job, +1.
j_random_hacker
+1  A: 

As far as I remember, there was the problem of reference counting pointer treated in a chapter of Effective C++.

In principle, you have the "light" pointer class, containing a pointer to a class holding the reference which knows to increment/decrement reference and destroy the pointer object. That reference counting class points to the object to be referenced.

Cătălin Pitiș
+13  A: 

I've seen two different non-intrusive approaches to this:

  1. The smart pointer allocates a small block of memory to contain the reference counter. Each copy of the smart pointer then receives a pointer to the actual object and a pointer to the reference count.
  2. In addition to an object pointer, each smart pointer contains a previous and next pointer, thereby forming a doubly-linked list of smart pointers to a particular object. The reference count is implicit in the list. When a smart pointer is copied, it adds itself to the list. Upon destruction, each smart pointer removes itself from the list. If it's the last one in the list it then frees the referenced object as well.

If you go here and scroll to the bottom, there is an excellent diagram which explains these methods much more clearly.

Ferruccio
This is the most correct answer.
John Dibling
A: 

Many answers address the way the reference count is stored (it is stored in a shared memory for all shared_ptr that hold the same native pointer), but most elude the problem of leaks.

The easiest way of leaking memory with reference counted pointers is creating cycles. As an example, a doubly linked list where all the pointers are shared_ptr with at least two elements is guaranteed not to be deleted. Even if external pointers are freed, the internal pointers will still count, and the reference count will not reach 0. That is, at least, with the most naïve implementation.

The easiest solution to the cycle problem is mixing shared_ptr (reference counted pointers) with weak pointers that do not share the ownership of the object.

Shared pointers will share both the resource (pointer) and the additional reference_count information. When you use weak pointers, the reference count is doubled: there is a shared pointer reference count and a weak pointer reference count. The resource is released whenever the shared pointer count reaches 0, but the reference_count information is left alive until the last weak pointer is released.

In the doubly linked list, the external reference is held in a shared_ptr, while the internal links are just weak_ptr. Whenever there are no external references (shared_ptr) the elements of the list are released, deleting the weak references. At the end all weak references have been deleted and the last weak pointer to each resources frees the reference_count information.

It is less confusing than the above text seems... I'll try again later.

David Rodríguez - dribeas