Doubly-linked list memory leak

#1

The doubly-linked list used in the book is defined as follows:

template <typename T>
struct BSTNode {
  T data;
  shared_ptr<BSTNode<T>> left, right;
};

However, this creates a cyclic dependency which will not allow any of the nodes to be destroyed. As an example:

template <typename T>
struct BSTNode {
  T data;
  shared_ptr<BSTNode<T>> left, right;

  BSTNode(T data) : data(data) {
    cout << "Created: " << data << endl;
  }

  ~BSTNode() {
    cout << "Destroyed: " << data << endl;
  }
};

int main() {
  auto a = make_shared<BSTNode<char>>('a');
  auto b = make_shared<BSTNode<char>>('b');

  a->right = b;
  b->left = a;

  return 0;
}

This can be resolved by making one of the pointers weak or raw.

0 Likes
#2

Hey Corwin,

You are right, that is the main weakness of shared_ptr. However, I don’t think there is any need to make one of the pointers weak or raw as both will have memory leak also due to “incorrect” implementation. Here, we assume you use doubly linked list correctly so we don’t worry that here.

0 Likes
#3

I believe the confusion may have come from me using BSTNode. The implementation of BSTNode is correct; however, the issue I mentioned is actually with ListNode, which uses the same ownership semantics. My example below will cause a memory leak:

template <typename T>
struct ListNode {
  T data;
  shared_ptr<ListNode<T>> prev, next;
  ListNode(T data) : data(data) {
    cout << "Created: " << data << endl;
  }
  ~ListNode() {
    cout << "Destroyed: " << data << endl;
  }
};

int main() {
  auto temp0 = make_shared<ListNode<int>>(0);
  auto temp1 = make_shared<ListNode<int>>(1);
  auto temp2 = make_shared<ListNode<int>>(2);
  auto temp3 = make_shared<ListNode<int>>(3);
  temp0->next = temp1;
  temp1->next = temp2;
  temp2->next = temp3;
  temp3->next = nullptr;
  temp0->prev = nullptr;
  temp1->prev = temp0;
  temp2->prev = temp1;
  temp3->prev = temp2;

  return 0;
}

When I was referring to making one of the pointers weak or raw, I meant in the ListNode, since that is the doubly-linked list.

0 Likes
#4

Hey Corwin,

I agree with your saying that example will cause memory leak. However, as I told before, we assume the usage here in EPI is proper use so we don’t want to worry this which will diverge your focus out from the main algorithm.

Similar logic can be applied to binary tree definition in EPI while we use unique_ptr. If you don’t use that properly, two unique_ptr points to same memory then a memory corruption might occur also. However, we don’t incorrectly use our unique_ptr so this is not something we are concerning here.

0 Likes
#5

Please explain how the usage of the doubly-linked list above is not correct. Note that this is not a contrived example, but is, in fact, a test case from the book. If you use that ListNode class in any proper example (more than one node), it will cause a memory leak when it goes out of scope.

0 Likes
#6

Hey Corwin,

Could you tell me which code is using this as I might need to fix those probably? I remember there is a singly linked list problem that involves cycle, and we deliberately do that due to problem description. I agree that it will cause problem and could be solved by using raw pointers. However, I don’t want to do that as I really want to use the power of smart pointers in this book, and hope you can understand that.

0 Likes
#7

I absolutely do understand, as the usage of C++11 is one of the great things about this book. The example was converting a sorted doubly-linked list to a BST. However, as I said, any example that uses that doubly-linked list will have the same issue.

I recommend making one of the two pointers weak or raw as this will represent unidirectional ownership.

0 Likes
#8

Hey Corwin,

I see the example you mentioned, and it makes sense that this will cause memory leak. However, your solution of making one of the two pointers weak or raw will cause memory corruption since the one pointed by shared_ptr will be destroyed automatically once the node holds shared_ptr is gone. The solution to this might be making both raw, and write codes to explicitly to free those afterwards. However, making this is similar to writing codes to explicitly breaks the bonds of shared pointers we have now, and I probably will prefer what I am doing now. Please let me know what you think, and I really appreciate you bring this up as I overlook this at that time indeed.

0 Likes
#9

Ah yes, of course. You are correct. I was thinking about list lifetime and not the individual nodes (which is obviously an important consideration).

In a production scenario, I would argue that the intention of raw pointers is clearer than shared_ptr’s that must be explicitly released. In an interview, I feel it would be reasonable to use either one with a discussion of the caveats.

0 Likes