CODEWITHSUNDEEP
c++smart-pointers
frozenca
frozenca

Reputation: 877

multiple shared_ptr that point to the same object

Just for studying purpose I'm coding binary search tree rotation now. I normally use std::unique_ptr but I used std::shared_ptr this time

This works correctly:

// Node implementation
template <Containable T = int> struct Node {
  T key_ = T{};
  bool black_ = false; // red-black tree
  std::shared_ptr<Node> left_;
  std::shared_ptr<Node> right_;
};

// this is a protected member function of red-black tree class
// xp is parent node of x
void left_rotate(Node *xp, Node* x) {
    assert(x);
    auto y = x->right_;
    x->right_ = y->left_;
    std::shared_ptr<Node> x_ptr;
    if (!xp) {
      x_ptr = root_;
      root_ = y;
    } else if (x == xp->left_.get()) {
      x_ptr = xp->left_;
      xp->left_ = y;
    } else {
      x_ptr = xp->right_;
      xp->right_ = y;
    }
    y->left_ = x_ptr;
  }

This crashes:

void left_rotate(Node *xp, Node* x) {
    assert(x);
    auto y = x->right_;
    x->right_ = y->left_;
    std::shared_ptr<Node> x_ptr(x);
    if (!xp) {
      root_ = y;
    } else if (x == xp->left_.get()) {
      xp->left_ = y;
    } else {
      xp->right_ = y;
    }
    y->left_ = x_ptr;
  }

cppreference says: Link

std::shared_ptr is a smart pointer that retains shared ownership of an object through a pointer. Several shared_ptr objects may own the same object. 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().

To avoid destroying the node pointed to by x before assigning, I created another std::shared_ptr<Node> that owns *x, but in the second implementation, the node object pointed by x is already destroyed before y->left_ = x_ptr is called. The node object is actually destroyed when one of root_ = y, xp->left_ = y and xp->right_ = y is called.

There are clearly multiple std::shared_ptr objects that own the same node object. root_, xp->left_ or xp->right_ is clearly NOT the last remaining std::shared_ptr owning the object. Why this happens?

Upvotes: 0

Views: 1995

Answers (1)

Goswin von Brederlow
Goswin von Brederlow

Reputation: 12322

void left_rotate(Node *xp, Node* x) {
    ...
    std::shared_ptr<Node> x_ptr(x);
    ...

When you create the shared_ptr it takes over ownership of x. The problem here is that it is not yours to give. Someone else, another shared_ptr, already has ownership of the pointer. So some of the operations you do before y->left = xptr will assign a new value to the shared_ptr owning x and that deletes the x.

The problem is that you use raw pointers as arguments. Whenever you extract the pointer from a shared_ptr be very careful about the lifetime of the object. The extracted raw pointer does not keep the object alive. Something that becomes exceedingly difficult to reason about with function calls. Easy to mess up as you experienced.

It's easily avoided by passing shared_ptr as arguments because they will keep your objects alive:

void left_rotate(std::shared_ptr<NodeY> xp, std::shared_ptr<Node> x) {

PS: I hope your root_ is a shared_ptr too.

Upvotes: 3

Related Questions