Where Is Shared_Ptr

Where is shared_ptr?

There are at least three places where you may find shared_ptr:

If your C++ implementation supports C++11 (or at least the C++11 shared_ptr), then std::shared_ptr will be defined in <memory>.
If your C++ implementation supports the C++ TR1 library extensions, then std::tr1::shared_ptr will likely be in <memory> (Microsoft Visual C++) or <tr1/memory> (g++'s libstdc++). Boost also provides a TR1 implementation that you can use.
Otherwise, you can obtain the Boost libraries and use boost::shared_ptr, which can be found in <boost/shared_ptr.hpp>.

Where is the reference count of an object typically stored?

It is "typically stored" in whatever location is necessary for the design of an object. Intrusive smart pointers require the T they're used with to provide the storage for the reference count. That's what makes them "intrusive"; they intrude on the object.

The design you outlined specified "can take an arbitrary object." Therefore, an intrusive design is off the table.

Since many instances of the smart pointer will have to have access to the same reference count object, that reference count must be independent of any one instance. And since it must also be independent of T, it therefore must be an object whose lifetime is independent of both T and any smart pointer instance that references it.

So the smart pointer, upon claiming ownership of a T, must also create the reference count object to manage it. Typically, this is done by heap allocating such an object. Copies of the smart pointer also get a pointer to the reference count.

This is also why it is illegal to have two different std::shared_ptr constructors claim ownership of the same T*. You can copy from a shared_ptr that already owns the T*, but you cannot just pass the T* itself directly to the constructor. Because T has no access to the reference count, shared_ptr's constructor would not know that someone else owns it, so it would create a second reference count block.

How is shared_ptr reference counter laid out?

The C++ Standard does not define for any non-standard-layout class how it should be laid out in memory, e.g. [class.mem]/13

Nonstatic data members of a (non-union) class with the same access control (Clause 11) are allocated so that later members have higher addresses within a class object. The order of allocation of non-static data members with different access control is unspecified (Clause 11). Implementation alignment requirements might cause two adjacent members not to be allocated immediately after each other; so might requirements for space for managing virtual functions (10.3) and virtual base classes (10.1).

There are some exceptions / simplifications for standard layout types, but there's no general specification for the memory layout of classes.

This also holds for the classes in the Standard Library. In addition to that, the Standard only defines requirements for these classes, some of those are "interfaces" in the sense of signatures of member functions. Very explicitly in [objects.within.classes]:

1) Clauses 18 through 30 and Annex D [i.e. the Standard Library] do not specify the representation of classes, and intentionally omit specification of class members (9.2). An implementation may define static or non-static class members, or both, as needed to implement the semantics of the member functions specified in Clauses 18 through 30 and Annex D.

2) Objects of certain classes are sometimes required by the external specifications of their classes to store data, apparently in member objects. For the sake of exposition, some subclauses provide representative declarations, and semantic requirements, for private member objects of classes that meet the external specifications of the classes. The declarations for such member objects and the definitions of related member types are followed by a comment that ends with exposition only, as in:
streambuf* sb; // exposition only

That said, some remarks for required functionality for std::shared_ptr:

you need to store the reference count for the owned object, in a dynamically allocated object which contains this ownership information (dyn. alloc. because it's not clear which shared_ptr is the last one alive, and this last one has to deallocate it)
you also need to store the reference count of this ownership information object for the use of weak_ptr, as weak_ptr::expired and weak_ptr::lock etc. may not fail (via an access violation, for example)

Pedantic side remark: The Standard doesn't require shared_ptr not to leak memory, but a typical implementation for PC-type architecture will probably use dynamic memory allocation.

std::make_shared btw is considered to be faster than using the ctor of std::shared_ptr because it can allocate the memory for both the owned object and the ownership information object in one allocation (the Standard says "Implementations should perform no more than one memory allocation.", though that is only a Remark).

Why is shared_ptr implemented using control block and not a static map?

So why does a committee decided to stick with a control block implementation?

It doesn't. The committee writes requirements that implementers must follow. They do not specify that std::shared_ptr be implemented in any particular way, so long as that way meets the requirements.

Having said that, your proposed static std::map<T*, size_t> runs foul of this general (unless otherwise specified) requirement:

A C++ standard library function shall not directly or indirectly
access objects ([intro.multithread]) accessible by threads other than
the current thread unless the objects are accessed directly or
indirectly via the function's arguments, including this.

[res.on.data.races#2]

Another compelling reason is that std::shared_ptr type-erases the deleter, so at best you'd have a static std::map<void *, struct { size_t count; size_t weak_count; std::function<void(void*)> deleter; }>, at which point you have two dynamic allocations for the control block, rather than the one (possibly merged with the owned object) that current implementers prefer.

Understanding when shared_ptr reference counts are incremented when passing into a function

std::move moves the item out of that variable into another one. As one author put it, it "has explicit license to pillage [the variable]." For most std objects, that puts the original object into an unspecified state. However, it appears std:shared_ptr is an exception in that it leaves the object in an empty state.

What all this boils down to is that you can't treat item as the same reference to s anymore after the move. It is in a different state, storing something else. That's why your reference count is off.

If instead you had done this:

std::cout << "useCount addItem post: " << items_.back().use_count() << std::endl;

You would have got the expected output of 2.

Question on converting boost shared pointer to standard shared pointer

The shared pointer created has a destroy function object (deleter) that has state. In particular it has a copy of the boost shared ptr.

The destruction action does nothing, it is the destruction of deleter that cleans up the boost shared ptr.

There is a problem though:

Does the C++ standard fully specify cleanup of the deleter itself? E.g. it might stay around when only weak references remain?
The standard does guarantee a minimum lifetime for the deleter, leaving the possibility that lives longer than that.

Destroying the destruction object is not specified to occur in either the constructor of std::shared_ptr nor the destructor of std::shared_ptr. It would be reasonable to destroy it either after it is called, or when the reference counting block is destroyed - in the second case, we end up with it lasting until the last weak ptr goes away.

From the draft standard:

[Note: It is unspecified whether the pointer remains valid longer than that. This can happen if the implementation doesn’t destroy the deleter until all weak_ptr instances that share ownership with p have been destroyed. — end note]

The possibility to defer destruction of the deleter is clear. So in that case we end up with shared_ptrs that doesn't destruct their element instance when we want it to be called depending on unspecified details of the C++ implementation you run it on. That is a bad idea.

Better Alternative

I would personally go with a similar trick based on the aliasing constructor instead. It is just as simple, has no additional overhead, and the semantics are actually correct:

template<class T>
std::shared_ptr<T>
as_std_shared_ptr(boost::shared_ptr<T> bp)
{
  if (!bp) return nullptr;
  // a std shared pointer to boost shared ptr.  Yes.
  auto pq = std::make_shared<boost::shared_ptr<T>>(std::move(bp));
  // aliasing ctor.  Hide the double shared ptr.  Sneaky.
  return std::shared_ptr<T>(pq, pq.get()->get());
}

This is much less of a hack than the code from the question, because lifetime
of the boost shared ptr is no longer tied to the (unspecified) lifetime of the deleter instance.

How is the std::tr1::shared_ptr implemented?

shared_ptr must manage a reference counter and the carrying of a deleter functor that is deduced by the type of the object given at initialization.

The shared_ptr class typically hosts two members: a T* (that is returned by operator-> and dereferenced in operator*) and a aux* where aux is a inner abstract class that contains:

a counter (incremented / decremented upon copy-assign / destroy)
whatever is needed to make increment / decrement atomic (not needed if specific platform atomic INC/DEC is available)
an abstract virtual destroy()=0;
a virtual destructor.

Such aux class (the actual name depends on the implementation) is derived by a family of templatized classes (parametrized on the type given by the explicit constructor, say U derived from T), that add:

a pointer to the object (same as T*, but with the actual type: this is needed to properly manage all the cases of T being a base for whatever U having multiple T in the derivation hierarchy)
a copy of the deletor object given as deletion policy to the explicit constructor (or the default deletor just doing delete p, where p is the U* above)
the override of the destroy method, calling the deleter functor.

A simplified sketch can be this one:

template<class T>
class shared_ptr
{
    struct aux
    {
        unsigned count;

        aux() :count(1) {}
        virtual void destroy()=0;
        virtual ~aux() {} //must be polymorphic
    };

    template<class U, class Deleter>
    struct auximpl: public aux
    {
        U* p;
        Deleter d;

        auximpl(U* pu, Deleter x) :p(pu), d(x) {}
        virtual void destroy() { d(p); } 
    };

    template<class U>
    struct default_deleter
    {
        void operator()(U* p) const { delete p; }
    };

    aux* pa;
    T* pt;

    void inc() { if(pa) interlocked_inc(pa->count); }

    void dec() 
    { 
        if(pa && !interlocked_dec(pa->count)) 
        {  pa->destroy(); delete pa; }
    }

public:

    shared_ptr() :pa(), pt() {}

    template<class U, class Deleter>
    shared_ptr(U* pu, Deleter d) :pa(new auximpl<U,Deleter>(pu,d)), pt(pu) {}

    template<class U>
    explicit shared_ptr(U* pu) :pa(new auximpl<U,default_deleter<U> >(pu,default_deleter<U>())), pt(pu) {}

    shared_ptr(const shared_ptr& s) :pa(s.pa), pt(s.pt) { inc(); }

    template<class U>
    shared_ptr(const shared_ptr<U>& s) :pa(s.pa), pt(s.pt) { inc(); }

    ~shared_ptr() { dec(); }

    shared_ptr& operator=(const shared_ptr& s)
    {
        if(this!=&s)
        {
            dec();
            pa = s.pa; pt=s.pt;
            inc();
        }        
        return *this;
    }

    T* operator->() const { return pt; }
    T& operator*() const { return *pt; }
};

Where weak_ptr interoperability is required a second counter (weak_count) is required in aux (will be incremented / decremented by weak_ptr), and delete pa must happen only when both the counters reach zero.

If I want to use std::shared_ptr, which header to include?

You'll find it in <memory> now.

Thread-safety of reference count in std::shared_ptr

Question 1:

The implementation linked to is not thread-safe at all. You are correct that the shared reference counter should be atomic, not pointers to it. std::atomic<int*> here makes no sense.

Note that just changing std::atomic<int*> to std::atomic<int>* won't be enough to fix this either. For example the destructor is decrementing the reference count and checking it against 0 non-atomically. So another thread could get in between these two operations and then they will both think that they should delete the object causing undefined behavior.

As mentioned by @fabian in the comments, it is also far from a correct non-thread-safe shared pointer implementation. For example with the test case

{
    Shared_ptr<int> a(new int);
    Shared_ptr<int> b(new int);
    b = a;
}

it will leak the second allocation. So it doesn't even do the basics correctly.

Even more, in the simple test case

{
    Shared_ptr<int> a(new int);
}

it leaks the allocated memory for the reference counter (which it always leaks).

Question 2:

There is no reason to have a null pointer check there except to avoid printing the message. In fact, if we want to adhere to the standard's specification of std::default_delete for default_deleter, then at best it is wrong to check for nullptr, since that is specified to call delete unconditionally.

But the only possible edge case where this could matter is if a custom operator delete would be called that causes some side effect for a null pointer argument. However, it is anyway unspecified whether delete will call operator delete if passed a null pointer, so that's not practically relevant either.

Where Is Shared_Ptr