unavoidable memory leaks when two nodes points to each other

Question

I am having a very strange problem with shared_ptr where two Node are using shared_ptr to point to each other.

I paste my test code and output valgrind first, then follow my understanding.

test code

#include <iostream>
#include <memory>

struct Node {
  int val_;
  std::shared_ptr<Node> next_;
  std::shared_ptr<Node> prev_;

  Node(int val)
      : val_(val), next_(nullptr), prev_(nullptr) {
  }
};

class List {
public:
  List() 
      : head_(nullptr){
  }

  void insert(int val) {
    auto new_node = std::make_shared<Node>(val);
    if (!head_)
      head_ = new_node;
    else {
      head_->next_ = new_node;
      new_node->prev_ = head_;
    }
  }

  void debug() {
    std::shared_ptr<Node> cur;
    for (cur = head_; cur != nullptr; cur = cur->next_)
      std::cout << cur->val_ << std::endl;
  }
private:
  std::shared_ptr<Node> head_;
};

int main(int argc, const char *argv[]) {
  List l;
  l.insert(199);
  l.insert(200);

  l.debug();

  return 0;
}

the output of valgrind.

==8282== Memcheck, a memory error detector
==8282== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==8282== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
==8282== Command: ./a.out
==8282== 
==8282== 
==8282== HEAP SUMMARY:
==8282==     in use at exit: 128 bytes in 2 blocks
==8282==   total heap usage: 2 allocs, 0 frees, 128 bytes allocated
==8282== 
==8282== 128 (64 direct, 64 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==8282==    at 0x4C28C90: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8282==    by 0x401825: __gnu_cxx::new_allocator<std::_Sp_counted_ptr_inplace<Node, std::allocator<Node>, (__gnu_cxx::_Lock_policy)2> >::allocate(unsigned long, void const*) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x401751: std::allocator_traits<std::allocator<std::_Sp_counted_ptr_inplace<Node, std::allocator<Node>, (__gnu_cxx::_Lock_policy)2> > >::allocate(std::allocator<std::_Sp_counted_ptr_inplace<Node, std::allocator<Node>, (__gnu_cxx::_Lock_policy)2> >&, unsigned long) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x4015B1: std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count<Node, std::allocator<Node>, int&>(std::_Sp_make_shared_tag, Node*, std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x4014FB: std::__shared_ptr<Node, (__gnu_cxx::_Lock_policy)2>::__shared_ptr<std::allocator<Node>, int&>(std::_Sp_make_shared_tag, std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x401451: std::shared_ptr<Node>::shared_ptr<std::allocator<Node>, int&>(std::_Sp_make_shared_tag, std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x40139D: std::shared_ptr<Node> std::allocate_shared<Node, std::allocator<Node>, int&>(std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x4011D2: _ZSt11make_sharedI4NodeIRiEESt10shared_ptrIT_EDpOT0_ (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x401000: List::insert(int) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x400DAC: main (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282== 
==8282== LEAK SUMMARY:
==8282==    definitely lost: 64 bytes in 1 blocks
==8282==    indirectly lost: 64 bytes in 1 blocks
==8282==      possibly lost: 0 bytes in 0 blocks
==8282==    still reachable: 0 bytes in 0 blocks
==8282==         suppressed: 0 bytes in 0 blocks
==8282== 
==8282== For counts of detected and suppressed errors, rerun with: -v
==8282== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 1 from 1)

understanding

|------|               |-------|
|next----------------->|next(nullptr)
|prev(nullptr)|<--------prev   |
|------|               |-------|
 head_                  new_node

I believe the reason why I am having the memory leaks is that when List's destructor gets called, it only reduce the reference to head_ by 1 rather than free the head_(because new_node->prev_ points to head_ as well). (maybe I am wrong?)

1> my question how to solve this problem.

Hope someone give me suggestions. thanks a lot.

Answer 1

You are correct. There are a lot of ways to fix this problem, but I recommend not allowing circles of strong pointers. One simple fix for this class is to make the forward pointer a strong pointer and the back pointer a weak pointer. That way, deleting the list will delete the only strong pointer to the head node, which will delete the only strong pointer to the second node, and so on.

When manipulating nodes in the list, make sure to hold your own strong pointers to the nodes you are manipulating to make sure they don't get destroyed while you are manipulating their forward pointers.

Answer 2

shared_ptr is not a panacea. You should ask yourself if each Node owns the next/previous Node.

An alternative is for List to own all the Nodes, and for the Node to link to other Nodes.

Semantically, shared_ptr and unique_ptr imply ownership, and * (or &) imply a relationship.

For a recent example of a different data structure, see Is there a more efficient implementation for a bidirectional map?. You can see that there's a nice split between managing the memory of the objects and managing the relationships between the objects.

Answer 3

You don't give much context, but if these are nodes of a graph, you probably don't want smart pointers at all. In such cases, the best solution is generally to let the graph object take care of all memory management of its nodes, since it (and only it) knows when a node is no longer used. shared_ptr is not a good solution here. (Note that none of the implementations of std::list that I've seen use shared_ptr.)