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
– Botje, Commented Aug 11, 2023 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 — pptaszni
– pptaszni, Commented Aug 11, 2023 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
– Quimby, Commented Aug 11, 2023 at 11:19
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
– Eljay, Commented Aug 11, 2023 at 11:29
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
– Konrad Rudolph, Commented Aug 11, 2023 at 11:50

Zacryon · Accepted Answer · 2023-08-12 01:59:29Z

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.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related