Smart pointers in doubly linked list

Question

I'm trying to implement smart pointers in doubly linked list (university task). Before that I've done the same task in pure C with raw pointers. The problem is when I add new Node to List by addNode() more than twice I have crash (I use CodeLite(g++), Windows 10 64bit). I assume that the problem is my memory management (destructors of Node and List). But I feel I don't have enough qualification to solve that. So any help will be appreciated.

#include <stdlib.h>
#include <iostream>
#include <memory>

using namespace std;

template <typename T>
struct Node       {

    T Value;
    weak_ptr<Node<T>> prev;
    shared_ptr<Node<T>> next;

    ~Node() {
        while (next){
            prev = next->next;
            next.reset();
            next = prev.lock();
        }
    }

 };


template<typename T>
class List 
{public:  

     shared_ptr<Node<T>> start;
     weak_ptr<Node<T>> end;
     int size;

 public:
     List(): size(0){};
     ~List();

     void addNode (T value);

 };


template <typename T> List<T>::~List() 
 {   
     cout<<"List destructor"<<endl;
     while (start){
         auto sp = end.lock();
         end = start->next;
         start.reset(sp.get());
     }
 }

template <typename T> void List<T>::addNode(T value){
    Node<T>* nd = new Node<T>;

    if (size==0){
        start.reset(nd);
        start->Value = value;
        end = start;

    }

    else{
        auto sp = end.lock();
        auto sp2 = end.lock();
        sp->next.reset(nd);
        sp.reset(sp->next.get());
        sp->prev = sp2;
        sp->Value = value;
        cout<<"Value size is "<<size<<" "<<sp->Value<<endl;
        end = sp;

    }

    size++;
    return;
}




int main ()
{
 system("CLS");

  string a;
  string b;
  string c;

  a = "1 test";
  b = "2 test";
  c = "3 test";


  List<string> ls;
  ls.addNode(a);
  ls.addNode(b);
  ls.addNode(c);

  return 0;

}

you don't need `shared_ptr` here. `unique_ptr` is the tool for the job if you want smart pointers. — bolov, Dec 19 '17 at 18:00
What is this? `start.reset(sp.get());` and `sp.reset(sp->next.get());` this is completely wrong way to deal with smart pointers — Slava, Dec 19 '17 at 18:03
@Slava there is only one owner for each node. The List object for the first node and the previous node for the rest. Ergo `unique_ptr` should be used. — bolov, Dec 19 '17 at 18:06
@bolov this is double linked list, where `weak_ptr` prev suppose to point to? — Slava, Dec 19 '17 at 18:07
@Slava The correct tool for the job, with only one owner per node, is to use a `unique_ptr` for the owner and a raw pointer (yes, a raw pointer; it’s standard for non-owning) for the back link. Since this is a university assignment I give at most a 50% chance the prof. understands that raw non-owning pointers are what seems to be the standard now; if not, then both need to be smart pointers for the assignment, and `shared`/`weak` is the way to go. — Daniel H, Dec 19 '17 at 18:38
If it stays in the Library Fundamentals v2, then [`observer_ptr`](http://en.cppreference.com/w/cpp/experimental/observer_ptr) and `unique_ptr` will be the right solution going forward, but IIRC some people on the committee dislike `observer_ptr` and it might not make it to the final standard. I hope it does, just because then there’ll be a clear semantic distinction between “This is a raw pointer; it is from legacy code or code with a very weird ownership model, and we don’t know who owns it” and “This is a non-owning pointer”. — Daniel H, Dec 19 '17 at 18:59
Good news! `list` already is a doubly linked list. Just use that. — Jonathan Mee, Dec 19 '17 at 19:32

Slava · Accepted Answer · 2017-12-19T19:09:47.833

1

The point of using smart pointers is automatic memory management, so your List and Node destructors not only badly implemented but also redundant. Just remove them (or make them empty). Your only task can be to implement addNode() properly:

template <typename T> void List<T>::addNode(T value){
    auto nd = std::make_shared<Node<T>>();
    nd->Value = value; // this should be done in Node constructor

    if (size++ == 0){
        start = nd;
    } else{
        auto sp = end.lock();
        nd->prev = sp;
        sp->next = nd;
    }
    end = nd;
}

When you deal with smart pointers normally you never call reset() and get() methods, only when you need to deal with raw pointers for various reasons (which is not the case here).

Note: as stated in the comment though empty destructors would work correctly there could be issue with long list due to recursive call so you may want to implement only List destructor to avoid that. Again this should be done without using reset() and get(), just working with smart pointers normally:

~List()
{
    while( start )
       start = start->next;
}

edited Dec 19 '17 at 19:09

answered Dec 19 '17 at 18:27

Slava

43,454
1
47
90

1

This doesn’t actually work well for long lists, because it will destruct the nodes recursively instead of in a loop, using O(n) memory and possibly causing a stack overflow (the bad kind, not this site). To get around that, you need a custom destructor for the list, but it is fairly simple. – Daniel H Dec 19 '17 at 18:39
I doubt this solution would be used for long lists, obviously this is a homework exercise. Anyway such destructor can be added later when program implemented and works properly for small lists. – Slava Dec 19 '17 at 18:42
A simple test driver could be `int main() {List l; for (int i = 0; i < 1000000; ++i) { l.addNode(i); }; return 0; /* Check if it supports large lists */}`. I don’t know what course the OP is taking, or where, but if this were a homework assignment in one of my CS courses I’d be shocked if that weren’t one of the tests. (Note that I don’t know what most implementations’ stack size is and a million might not be enough, but it’s trivial to increase that number.) – Daniel H Dec 19 '17 at 18:45
@DanielH added List destructor – Slava Dec 19 '17 at 19:10
@Slava holy shit, it helped! Thanks a lot. Can you please suggest me the good source about all this memory-managment theme in c++ especially about destructors? – User88 Dec 19 '17 at 20:09
@User88 any good C++ book should explain that: https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list – Slava Dec 19 '17 at 20:11

Smart pointers in doubly linked list

1 Answers1