Do I have to remove all references to an object using std::shared_ptr

Question

So, as a hundreds of thousands of people before me, I am implementing a doubly linked list in С++. Here's a Node and List struct:

struct Node {
    std::shared_ptr<Node> prev, next;
    int data;

    Node(int data) : data(data), next(nullptr), prev(nullptr){};
    Node(int data, std::shared_ptr<Node> prev, std::shared_ptr<Node> next)
        : data(data), prev(prev), next(next){};

    ~Node(){};
};

struct List {
    std::shared_ptr<Node> head, tail;
    size_t size;
    
    // some methods ...
    void remove(int data);

    List();
    List(std::initializer_list<int> list);
    List(size_t s, int data = 0);
    ~List();
};

As you can see, I'm using shared pointers to store next and previous nodes.

So now I'm implementing remove method of List and I wondered whether it is necessary for the node to be deleted to nullify its next and prev pointers. It should be smth like this:

// value - desired number to remove
if (curr->data == value) {
    curr->prev->next = curr->next;
    curr->next->prev = curr->prev;

    std::shared_ptr<Node> tmp = curr;
    curr = curr->next;
    tmp->prev = nullptr;
    tmp->next = nullptr;
    tmp = nullptr;

    size--;
}

Here is an illustration:

There's not much point to it. Once the last reference to `tmp` goes out of scope all of its members are destructed, which automatically resets `prev` and `next`. — Botje, Aug 11 '23 at 11:14
Assuming the only references to your current node are: `curr`, `prev->next`, and `next->prev`, the first 2 lines are enough, you don't need to nullify pointers of `curr` because it will be destroyed once it goes out of scope anyway. However, if you implement a list using `shared_ptr`, be aware of [cyclic dependencies](https://stackoverflow.com/questions/22185896/what-is-the-cyclic-dependency-issue-with-shared-ptr) — pptaszni, Aug 11 '23 at 11:17
Be careful that `std::shared_ptr` will not deallocate a double-linked list properly because no reference count is ever zero. — Quimby, Aug 11 '23 at 11:19
@pptaszni but if I want to completely clear the list I have to make sure that there are no more references to any node allocated. If I do not nullify the pointers to the prev and next, then the reference counter to these objects will not be set to zero — lian, Aug 11 '23 at 11:28
I'd use a unique_ptr to the next, and a raw (non-owning) pointer to prev. Alternatively, the destuctor for the linked list is responsible for walking the list and unlinking each node (which will destruct the node). (Even if using unique_ptr, should still walk the list and unlink each node, to prevent stack overflow via recursion of destructors.) — Eljay, Aug 11 '23 at 11:29
@Eljay I already wrote a destructor to completely clear the list. But If I want to only remove nodes with a given value I have to do immediately when deleting — lian, Aug 11 '23 at 11:36
Or you have the `List` own all the nodes, and have raw pointers for `prev` and `next` — Caleth, Aug 11 '23 at 11:36
`shared_ptr` denotes *shared* ownership of the resource. This usually isn’t an appropriate model for your use-case. The way ownership works in a linked list is generally with a *single* owner (= the list). Alternative models are thinkable (e.g. as suggested by Eljay) but I’d argue that none of them are convenient or natural. — Konrad Rudolph, Aug 11 '23 at 11:50
If this is a self practice, `Node` is implementation detail for `List`; thus I'd make it a private member type. The ownership of `Node` instances belongs to a `List` instance; so, I'd define `Node` as an aggregate type with raw pointers. A later revision would use an allocator for `List` and retrieve pointer types from the allocator. `shared_ptr` is just an improper complication, because you want to reinvent the wheel. In either case, `Node` is not supposed to control the life-time of its neighbors; the `List` object is in charge. — Red.Wave, Aug 11 '23 at 17:35
This is just funny. The whole point of `shared_ptr` is to let you stop worrying about ownership. But in this case it's making you worry **more**. — Mark Ransom, Aug 12 '23 at 01:05

score 2 · Accepted Answer · answered Aug 12 '23 at 01:59

It depends on what you want to do.

Do you want the users of your list to be able to hold references to node objects in memory even if the list has already removed them (instead of "just" the payload data)? In that case these lines are sufficient:

if (curr->data == value) {
    curr->prev->next = curr->next;
    curr->next->prev = curr->prev;

    size--;
}

(But you might also want to nullify the prev and next pointers as I will explain later.)

The node object which was previously managed by the list is only destroyed and deallocated if no other shared_ptr instance holds a reference to it anymore. I leave the explanation to cppreference.com:

The object is destroyed and its memory deallocated when either of the following happens:

the last remaining shared_ptr owning the object is destroyed;

the last remaining shared_ptr owning the object is assigned another pointer via operator= or reset().

See: https://en.cppreference.com/w/cpp/memory/shared_ptr

This is fine if the users of your list should be able to keep the node object in memory.

But if you absolutely want to destroy the node object when you remove it from the list, even if users of the list have accessed the node, you might need to rethink the design of your list. There are several ways to approach this.

One (usually really bad) way, when using shared pointers, is of course deleting all remaining shared pointers which are managing the node. But that might become very tedious and infeasible, since you need means to maintain reachability to those references from the list. And you can hardly influence what users of your list will do with their shared pointers. So basically you can forget this approach alltogether.

You could look into the use of weak pointers, which create a "temporary" shared pointer reference to an object, see: https://en.cppreference.com/w/cpp/memory/weak_ptr .

Or you manage the nodes without using shared pointers. Your nodes would hold references to other nodes, e.g., by raw pointers Node* (mind memory management!) or by using unique pointers, see: https://en.cppreference.com/w/cpp/memory/unique_ptr . However, using unique pointers will only work from one side (only one reference allowed). Be aware not to accidentally casting a unique_ptr to a shared_ptr.

In any case, don't forget to mind the node object you are returning to a user. If you want to keep the node in memory, but just remove it from the list (like in the first case), you need to nullify the next and prev pointers of the node, i.e., set them to nullptr. (As you did before.) Otherwise you would have a node outside of your list which would have access to the list as if it were a node. This conflicts with the intutive use of a list and could create some nasty bugs and spaghetti code.

But if you are never going to return shared pointers to node objects of your list to users in any way, you don't need the nullification of prev and next of the current node as it will be destroyed after all shared references to it are reset. And since there will only be two shared pointers to a node, this is easily managable. And usually you don't return list node objects to users, but rather (hard) references of the objects the nodes are holding.

Do I have to remove all references to an object using std::shared_ptr

1 Answers1