Double Linked List with smart pointers: problems with insert method

Question

I'm trying to implement a Templated Double Linked List, following Stroustrup's book "Principles and Practice using C++", Chapter 20.4. Instead of raw pointers, I want to use unique pointers. The code is organized as follows:

• header Node.h where the struct Node is implemented: a unique_pointer is used for the next node, and a raw one for the previous
• header Iterator.h where the Iterator is implemented
• header List.h where the class List is implemented
• a main.cpp where the methods are tested

I've seen that there have been other pretty similar questions, like this one but I don't know if the design of my insert method: iterator insert(iterator p, const T& x) is okay. In particular, I obtain a segmentation fault if I call auto it3 = insert(--p,4). Is this okay, or should I fix this?

Here's my Node.h

#ifndef Node_h
#define Node_h

#include <algorithm>
#include <iostream>
#include <memory>  // std::unique_ptr
#include <utility> // std::move



namespace Node {


template <typename T>
struct Node {
    T data;
    std::unique_ptr<Node> next;
    Node* previous;
    
    Node() noexcept = default;
    explicit Node(const T& _data) : data{_data}, next{nullptr},previous{nullptr} {
        std::cout << "l-value"<<std::endl;
    }
    Node(const T& _data, Node* _next, Node* _previous): data{_data}, next{_next}, previous{_previous} {}

    explicit Node(T&& x) : data{std::move(x)} {
      std::cout << "r-value" << std::endl;
    }
    
    Node(T&& x, Node* _next, Node* _previous) : data{std::move(x)}, next{_next}, previous{_previous} {
      std::cout << "r-value" << std::endl;
    }
    
    explicit Node(const std::unique_ptr<Node> &x) : data{x->data} {
        if (x->next){
        next.reset(new Node{x->next});
        }
//        if (x->previous){
//            previous.reset(new Node{x->previous});
//        }
    }
    
    
    
    ~Node()=default;
    
    //Move semantics, Copy semantics
    
    void printNode(){
        std::cout << "Data is: " << data <<"\n";
    }
    
 };

} //end namespace

#endif /* Node_h */

Then, here's the Iterator.h

#ifndef Iterator_h
#define Iterator_h

#include "Node.h"
#include <iterator>

template <typename T >
struct __iterator {;
    using NodeT = Node::Node<T>;
    NodeT* current;
    
//public:
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
    using reference = value_type&;
    using pointer = value_type *;
    
    explicit __iterator(NodeT* p) : current{p} {}
    __iterator() noexcept=default;
    ~__iterator()=default;
    
    reference operator*() const noexcept{
        return current->data;
    }
    
    pointer operator->() const noexcept{
        return &**this;
    }
    
    __iterator& operator++() {
      current = current->next.get();
      return *this;
    }
    
    __iterator& operator--(){
        current=current->previous; //previous is just a raw pointer
        return *this;
    }
    
    
    
    friend bool operator==(__iterator &a, __iterator &b) {
      return a.current == b.current;
    }
    

    friend bool operator!=(__iterator &a, __iterator &b) { return !(a == b); }
};

#endif /* Iterator_h */

Here's the header List.h

#include "Iterator.h"
#include <cassert>

template <typename T>
class List {
private:
    std::unique_ptr<Node::Node<T>> first;
    std::unique_ptr<Node::Node<T>> last;
    int _size;
public:
    
    
    using iterator = __iterator<T>;
    
    iterator begin(){return iterator{first.get()};}
    iterator end(){return iterator{nullptr};} //one past the last
    
    iterator go_to(const int n){
        assert(n>=0);
        int i=0;
        if (n < _size) {
            auto tmp{begin()};
            while (i<n) {
                ++tmp;
                ++i;
            }
            return tmp;
        }else{
            return iterator{nullptr};
        }
    }

    List() : first{nullptr}, last{nullptr},_size{0} {}
    ~List() noexcept = default;
    
    
    template <typename O>
    void push_front(O &&x) { // forwarding ref. not r-value

        first.reset(new Node::Node<T>{std::forward<O>(x),first.release(),nullptr});
        if (_size==0) {
            last.reset(nullptr);
        }
        
        ++_size;
    }
    
    template <typename O> //forward reference
    void push_back(O&& x){
        auto tmp = first.get();
        auto _node = new Node::Node<T>{std::forward<O>(x)};
        if (!tmp) {
            first.reset(_node);
            return;
        }

        while (tmp->next) {
            tmp = tmp->next.get();
        }
        tmp->next.reset(_node);
        ++_size;
    }
    
    
    iterator substitute(iterator p, const T& x){
        //_size must not be incremented!
        iterator tmp{p};
        if(tmp.current){
            *tmp = x;
            return tmp;
        }else{
            return iterator{nullptr};
        }

    }
    
    iterator insert(iterator position,const T& value) {
        auto newNode = new Node::Node<T>(value, position.current->next.get(), position.current);
        std::cout << position.current << std::endl;
        if (position.current == last.get() ) {
            last.reset(newNode);
        }
        
        position.current->next.release(); //otherwise: "pointer being freed was not allocated"
        position.current->next.reset(newNode); //set next of previous node to newNode
        ++_size;
        return position;
    }
    

    

    
    friend std::ostream& operator<<(std::ostream& os, List& l){
        auto itStop = l.end();
        os << "The list has " << l._size << " elements"<<"\n";
        for (auto it = l.begin(); it!=itStop; ++it) {
            os<< *it << " ";
        }
        return os;
    }
    
};

Finally, here's the main.cpp file with the tests:

#include "List.h"

int main() {

    
    List<int> l{};

    int i=8;
    l.push_front(i); //l-value
    l.push_back(4); //r-value
    l.push_back(i+2); //r-value
    l.push_back(95); //r-value
    l.push_front(29); //l-value
    l.push_front(i*i); //r-value
    std::cout << "My list so far: " << l<<std::endl;

    auto p{l.go_to(3)};
    auto itt = l.substitute(p, 29);
    std::cout << "My list after substitution: \t" << l<<std::endl;

    auto pp{l.go_to(2)};
    auto it2 = l.insert(pp,98);
    std::cout << "My list after insertion: \t" << l<<std::endl;
    auto it3= l.insert(--pp,998);
    std::cout << "My list after insertion: \t" << l<<std::endl;
    
    return 0;
}

EDIT:

Corrected version of push_front:

template <typename O>
void push_front(O&& x) {
    auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
    std::swap(node, first);  
    first->next = std::move(node);
    if (_size == 0) {
        assert(!last);
        assert(!first->next);
        last = first.get();
    }else{
first->next->previous = first.get()
}
    ++_size;
}

Answer 1

You have a number of problems with memory management in this linked list. The key thing to remember is that unique_ptr indicates ownership of an object. Use of release, reset, and to a lesser extent get are a code smell: not always wrong, but often an indication that the class is being used incorrectly. Usually you should use swap and move-assignment instead. I'll call these out as I work through the files.

A quick note: I have not tested or even compiled the following code; it may contain some errors.

Node.h

This is mostly fine. The "copy" constructor (Node(std::unique_ptr<Node>&)) probably should just be removed. It doesn't really make sense to copy a node and all its descendants. Even if you wanted that behavior, this implementation is buggy. It removes all the previous links, so that you've got a singly linked list that pretends to be a double linked list.

Iterator.h

Your iterator class is not quite right. It doesn't work as an end iterator. In particular, --l.end() exhibits undefined behavior because it dereferences a null pointer. In practice, iterator classes tend to need a reference to the collection that they come from.

In addition, this iterator does not meet the requirements of a bidirectional iterator (I know you mark this as a forward iterator, but it also does not meet those requirements). In particular, it violates:

• "lvalues of type It satisfy Swappable"; I'm a little rusty here but I'm pretty sure your user-declared destructor prevents the implicitly declared move constructor and move assignment operator from being generated; you must either provide those functions (e.g. using = default) or a swap function.
• It does not support the postfix increment and decrement operators.

List.h

List::last isn't really implemented correctly. As far as I can make out, it's never actually set to anything other than nullptr by the code as is. In any case, this should not be a unique_ptr, because anything it points to is already owned by another unique_ptr.

So let's change last to a Node::Node<T>*. We have the following invariants that are true before and after each member function exits: If _size == 0, first==last==nullptr. Otherwise,

• first points to the first node in the list
• first->previous == nullptr
• Given a reachable node n, n->next is null or n->next.get() == n->next->previous
• last points to the last reachable node in the list. last.next is null.
• _size nodes are reachable.

We need to write our member functions so that these invariants remain true.

go_to would usually be achieved through applying std::next to the begin iterator. That has a difference of behavior when you're trying to go past the end of the list; using std::next would result in undefined behavior in that case. If you want the current behavior you could implement it with something like

iterator go_to(const int n) const {
    if (n >= _size) {
        return end();
    } else {
        return std::next(begin(), n);
    }
}

When you're using unique_ptr to manage memory, you should generally not use new. Instead, use std::make_unique if you're using C++14 or later (and write your own make_unique in C++11). This allows you to improve the exception safety of your code. Try this for push_front:

template <typename O>
void push_front(O&& x) {
    auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
    swap(node, first);  // assuming you implement swap or add a "using std::swap;" on the previous line
    first->next = std::move(node);
    if (_size == 0) {
        assert(!last);
        assert(!first->next);
        last = first.get();
    }
    ++_size;
}

Here, node is created in an exception-safe manner. There is no chance of leaking first, since we do not release it (your code would leak first if the allocation failed or if Node's constructor threw (due to T's move constructor throwing)). Assuming your swap and move are no-throw operations, either push_front succeeds, and the new element has been inserted at the beginning, or the allocation fails, push_front throws, and the data structure has not been changed.

As for push_back, if you're not using last here, there's no reason to have last at all.

template <typename O>
void push_back(O&& x) {
    auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
    if (_size == 0) {
        assert(!last);
        assert(!first);
        first = std::move(node);
        last = node.get();
        _size = 1;
        return;
    }
    assert(!last->next);
    node->previous = last;
    last->next = std::move(node);
    last = last->next.get();
    ++_size;
}

Again, we ensure that the class's invariants hold, even if we throw while constructing the new node.

I don't think substitute is a reasonable function. Your list's user should write *it = x; and they should know whether their iterator is valid or not.

The normal semantics for insert are to insert a value just before the iterator passed in, not just after. This allows insert to insert at any position in the list and it means that insert has sensible semantics when end() is passed as the iterator.

iterator insert(iterator it, const T& value) {
    auto node = std::make_unique<Node::Node<T>>(value);
    auto prev = it.current ? it.current->previous : last;
    auto ptr = prev ? &first : &prev->next;
    swap(*ptr, node);
    (*ptr)->next = std::move(node);
    (*ptr)->previous = prev;
    ++_size;
    if (!last) last = first.get();
    return iterator(ptr->get());
}

Answer 2

Move class Node and struct __iterator into class List

It is very weird to see Node::Node<T> inside the code. A Node is an implementation detail of your List, so it should be declared inside class List. The same goes for __iterator. For example:

template<typename T>
class List {
    class Node {
        T data;
        std::unique_ptr<Node> next;
        Node *previous;
    };
    
    std::unique_ptr<Node> first;
    std::unique_ptr<Node> last;
    ...

public:
    class iterator {
         Node *current;

    public:
         using value_type = T;
         ...
    };

    iterator begin() {...};
    ...
};

Notice how all this avoids needing to introduce namespaces or __ prefixes (which you should avoid) to hide them, and how this reduces the number of times you have to explicitly write <T>. Of course, now everything has to be declared inside List.h, but I don't see that as a drawback.

Answer 3

I think you should follow C++ standard insert for containers by passing a begin and end iterator, for example

template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);