Learning smart pointers

[thisisbasil]

Ok, so I was taught basic, raw, C++98 when I was coming up. I figure its about time to shake off the bit rust and learn some of the newer features, progressing to 11, 14, and 17 this year.

I am now trying to understand smart pointers. I will enumerate some of my errors/misunderstandings below, using a simple linked link class. Questions will be comments

  template <class T>
  class LinkList
  {
  private:

    struct node
    {
      T data;
      node* next;
    };
    // I think I should be using a shared pointer here
    shared_ptr<node> head;
    shared_ptr<node> tail;
    int size;

  public:
    LinkList()
    {
      size = 0;
      /* 
      the following two lines give me compilation errors, and I am not sure why
      i also am under the understanding that i can reset it to a raw, null value
      */
      head.reset(nullptr);
      tail.reset(nullptr);
    }

    void insert_front(T t)
    {
      shared_ptr<node> temp(new node);
      temp->data = t;
      // compiler error, not sure why. if i change it to head.get() it "works"
      temp->next.reset(head);
      size++;
      if (size == 1)
      {
        tail.reset(temp);
        // compilation error
        tail->next.reset(nullptr);
      }
    }

    // segmentation fault, if i massage compilation errors with .get()
    friend ostream& operator<< (ostream& stream, const LinkList<T>& ll)
    {
      stream << '[';
      // compilation error
      shared_ptr<node> curr(other.head);
      while(curr.get())
      {
        cout << ' ' << curr->data << ' ';
        /*
           compilation error
           however, it compiles when i write the following:
               curr.reset((curr.get())->next.get());
        */
        curr.reset(curr->next);
      }
      stream >> ']';
      return stream;
    };
  };

I hope that is clear, I can clarify as much as needed. The class is pretty simple. I am first off not sure I am using the correct type of smart pointer...

[mbozzi]

Smart pointers are only intended to model ownership of a given resource. Every resource has at least one owner; those owner(s) are the objects potentially responsible for releasing that resource. As the names suggest, shared_ptr models ownership shared between multiple owners, and unique_ptr models sole ownership. In this model, plain pointer types (raw pointers) do not own the resource they point to.

Your current design doesn't save you anything (you still need the to follow the rule of three) and the code is more complicated as a result. This is because the head and tail nodes don't own the next nodes in the list, meaning that those intermediate nodes will not be copied nor released by default. One way to avoid that might involve making the next pointer (node::next) a smart pointer -- a unique_ptr, preferably.

This suggests a singly-linked structure which looks something like this:

class list { 
  struct node { std::unique_ptr<node> next; /* etc. */ }; 
  std::unique_ptr<node> head; // smart pointers are empty by default 
  node* tail = nullptr;  // CppCoreGuidelines C.48 ( https://goo.gl/wLyadq )
  // etc.
};

unique_ptr is used because there is no shared ownership at all. The above structure implies that the container owns the head of the list, and each node in the list owns the next node. The tail is there only to make insertion at the end easier, and so the tail is not an owning pointer.

This still isn't a perfect structure for two main reasons -- one subtle, one not so much. The not-so-subtle error is a semantic one: according to the ownership semantics of smart pointers, every node owns the following one, and the list itself only owns the last node by proxy through an arbitrary number of other nodes. This is probably a mistake: this container is not intrusive, so the container is directly responsible for each node.

The more subtle problem is that this structure is prone to stack-overflow through recursive destruction of the entire ownership list -- when node n is destroyed, n->next will be destroyed recursively. This process consumes linear stack space in the length of the list, which is serious enough to disqualify the design in many circumstances.

[48T7M4Gy]

https://stackoverflow.com/questions/106508/what-is-a-smart-pointer-and-when-should-i-use-one

[Cubbi]

Ok, so I was taught basic, raw, C++98 [...] I am now trying to understand smart pointers.

If you know C++98, then C++11's std::unique_ptr is just like C++98's std::auto_ptr, except it can be put in a vector. std::unique_ptr was purposefully designed as a direct drop-in replacement for std::auto_ptr (and fixing auto_ptr was one of the main motivations behind C++11's move semantics).

C++11's std::shared_ptr is the same idea as what was already popular and proposed for standardization in 1994 but didn't make the 1998 standard, so it was a part of boost since then, but I suppose "raw C++98" means no boost.. so yes, see that stackoverflow link above, and also references such as http://en.cppreference.com/w/cpp/memory/shared_ptr http://en.cppreference.com/w/cpp/memory/unique_ptr and http://en.cppreference.com/w/cpp/memory/weak_ptr

There are also a few relevant guidelines in https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md

mbozzi is right, there is certainly no reason to use std::shared_ptr in template <class T> class LinkList. There are no multiple owners of head (or of tail) that are in different threads of execution or otherwise destroyed in indeterminate order.