shared_ptr does not destruct the object at the end of the program

Question

I'm trying to implement a Deque using smart pointers. However, I noticed that at the end of the program the Nodes of the Deque are not destructed properly.
Here is the code:

#include<iostream>
#include<memory>


class Node
{
  int value;
  std::shared_ptr<Node> next = nullptr;
  std::shared_ptr<Node> prev = nullptr;

public:
  Node() = default;
  Node(int val): value(val) {}
  ~Node()
  {
    std::cout << "Destructor of node: " << value << std::endl;
  }
  friend class Deque;
};

class Deque
{
  using pointer = std::shared_ptr<Node>; 
  pointer head = nullptr;      // pointer to the first element of the queue
  pointer tail = nullptr;      // pointer to the last element of the queue 

public:
  Deque() = default;
  ~Deque(){ std::cout << "Dequeue destructor" << std::endl; }
  
  bool is_empty()
  {
    if (head == nullptr && tail == nullptr )
      return true;
    else
      return false;
  }
  void push_back(const pointer& val)
  {
    if (is_empty())
      {
        head = val;
        tail = val;
      }
    else
      {
        val->prev = tail;
        tail->next = val;
        tail = val;
      }
  }
};



int main()
{
  Deque DEQ;  
  auto node1 = std::make_shared< Node >(1);
  auto node2 = std::make_shared< Node >(2);
  auto node3 = std::make_shared< Node >(3);

  DEQ.push_back(node1);
  DEQ.push_back(node2);

  std::cout << "Use count node1 = " << node1.use_count() << std::endl;
  std::cout << "Use count node2 = " << node2.use_count() << std::endl;
  std::cout << "Use count node3 = " << node3.use_count() << std::endl;
 
  return 0;
}

The output is the following:

Use count node1 = 3
Use count node2 = 3
Use count node3 = 1
Destructor of node: 3
Dequeue destructor

when I push the node1 and node2 into the Deque, they are not destructed at the end of the program, while node3 is correctly destructed.
I assume the problem is that the reference count of node1 and node2 is equal to 3. Do you know how I can change my implementation in order to solve this problem? Thanks.

See this similar [question](https://stackoverflow.com/questions/36673391/c-linked-list-using-smart-pointers) that uses lists. — 1201ProgramAlarm, Oct 09 '20 at 14:54
`std::shared_ptr next = nullptr; std::shared_ptr prev = nullptr;` is a classical shoot in your own foot. ;-) One of them should be a `std::weak_ptr`. (I would vote for `prev`.) — Scheff's Cat, Oct 09 '20 at 14:54
If you build up a double-linked list with this, every node will own it's next as well as the next will own its predecessor. This produces a cycle and no one will be able to give up the ownership (without external intervention). This is a typical memory-leak produced by cyclic ownership. — Scheff's Cat, Oct 09 '20 at 14:56
When an object has a pointer to its owner, that pointer does not need to be a smart pointer because there is no lifetime concern. — François Andrieux, Oct 09 '20 at 15:00

score 3 · Accepted Answer · answered Oct 09 '20 at 14:58

I assume the problem is that the reference count of node1 and node2 is equal to 3.

Your assumption is correct. Shared pointers do not destroy the pointed object until ref count drops to zero.

Do you know how I can change my implementation in order to solve this problem?

Don't have cycles in your ownership graph. You could for example use owning smart pointers in one direction of your list, and non-owning pointers (perhaps weak pointers) in the other direction.

shared_ptr does not destruct the object at the end of the program

1 Answers1