2

If we have some smart pointer class that can take an arbitrary object and provide a reference counted pointer, how do we go about actually storing the integer that counts the references? The reference count has to be shared among all instances of the smart pointer class that point to the same object.

One solution I thought of was storing the reference count in the object that we are pointing to, but that isn't very nice for a general solution since every object would have to have either provide the reference count itself or inherit from some object that provides it.

Jabberwocky
  • 48,281
  • 17
  • 65
  • 115
screeb
  • 625
  • 6
  • 20
  • 1
    A `shared_ptr` needs not literally have a `T*`. It can have a `reference_count_block_with*`, which contains both a reference count _and_ a `T` – KABoissonneault Jun 20 '19 at 19:26
  • Why not with the smart pointer class itself? https://stackoverflow.com/questions/9200664/how-is-the-stdtr1shared-ptr-implemented – Avin Kavish Jun 20 '19 at 19:27

3 Answers3

5

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.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
1

The general solution used by std::shared_ptr is to allocate a separate control block, which holds the reference count (and other things as well, e.g: destructor, weak_ptr count).

(The control block and the object can live in the same allocation if std::make_shared is used)

The thing you describe in the second paragraph also exists, e.g: it is called intrusive_ptr in Boost.

erenon
  • 18,838
  • 2
  • 61
  • 93
1

There are many strategies for storing the reference count, depending on what operations you'd like to support.

The other answers here have outlined one option, which is to allocate an auxiliary control block alongside the managed memory and to have all the smart pointers point to that auxiliary block. This makes it easy to quickly determine the exact reference count, but requires an extra allocation per smart pointer, which can slow things down a bit and may fail if memory is scarce. (There's also issues about cache friendliness of looking up control blocks when they're not stored contiguously with the object itself).

Another option is reference linking, in which there is no explicit reference count. Instead, you thread a circularly, doubly-linked list through all of the smart pointers. When adding a new smart pointer to the object, that smart pointer is spliced into the linked list, and when removing a smart pointer, the smart pointer is spliced out of the linked list. This eliminates the need for an auxiliary allocation (unless, say, you need a custom deleter) and improves locality, but makes it expensive to determine the exact reference count. It's somewhat uncommon to actually need the exact reference count, so this tradeoff is often a reasonable one to make.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • How exactly would one obtain the count in such a scenario? – Avin Kavish Jun 20 '19 at 20:12
  • Since everything is wired in a circular list, you essentially would just walk the linked list until you end up back where you started, counting the number of steps you took along the way. – templatetypedef Jun 20 '19 at 20:13
  • @AvinKavish: It should also be noted that you almost *never* actually want a count. The most you might want to ask for is if it is the only pointer holding ownership. – Nicol Bolas Jun 20 '19 at 23:19