Generic doubly linked list copy constructor efficiency and linkage-CodePudding

I am having an issue with implementing the following two constructors:

List(const List& other)
~List()

Originally, the copy constructor was written as:

for (auto current = other._head._next; current != &other._head; current = current->_prev){
            push_back(static_cast<T*>(current));
        }

The above is considered ineffective and inefficient. So, I am trying to re-write it like this:

for (auto ptr = other._head._next; ptr != &other._head; ptr = ptr->_next)
        {
            T* item = new T(*dynamic_cast<T*>(ptr)));

            Link<T>* current = &_head;
            Link<T>* previous = &_head;

            current->_next = item;
            previous = current;

            /*
            
            // link to new head
            _head._next = other._head._next;
            _head._prev = other._head._prev;

            // Link prev och next to correct head
            _head._next->_prev = &_head;
            _head._prev->_next = &_head;
            
            */
        }

However, I am a total newbie on understanding how this Next, Prev, Next Prev, and finally connect together has to be done properly in the context of this copy constructor and the destructor. So, I am not sure why the above does not work and I am asking if someone know this and can help out here.

Link.hpp

template<class T>
class Link {
    template<class> friend class List;
    Link* _next, * _prev;
public:
    Link() : _next(this), _prev(this) {}
    virtual ~Link() {}
    T* next() const { return dynamic_cast<T*>(_next); }
    T* prev() const { return dynamic_cast<T*>(_prev); }

    T* insert_after(T* in)
    {
        in->_next = this;
        in->_prev = m_prev;
        _prev->_next = in;
        _prev = in;
        return in;
    }

    T* insert_before(T* in)
    {
        return _prev->insert_after(in);
    }

    T* remove()
    {
        _prev->_next = _next;
        _next->_prev = _prev;
        return dynamic_cast<T*>(this);
    }

    void splice_after(Link* f, Link* l)
    {
        if (f != l){
            f->_prev->_next = l->_next;
            last->_next->_prev = f->_prev;

            f->_prev = this;
            l->_next = this->_next;
            _next->_prev = l;
            _next = f;
        }
    }

    void splice_before(Link* f, Link* l)
    {
        m_prev->splice_after(f, l);
    }

    T* erase_first()
    {
        Link* tmp = _next;
        _next = _next->_next;
        _next->_prev = this;
        return static_cast<T*>(tmp);
    }

    T* erase_last() {
        Link* tmp = _prev;
        _prev = _prev->_prev;
        _prev->_next = this;
        return static_cast<T*>(tmp);
    }
};

List.hpp:

#include <string.h>

template<class T> 
class List {
    template<class X> class ListIter {
        template<class> friend class List;
        Link<T>* _ptr;
    public:
        // Typedefs
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef ptrdiff_t difference_type;
        typedef std::remove_const_t<X>  value_type;
        typedef X* pointer;
        typedef X& reference;
    public:
        ListIter() : _ptr{ nullptr } {}
        ListIter(Link<T>* ptr) : _ptr{ ptr } {}
        ListIter(const ListIter& other) : _ptr{other._ptr} {}
        ListIter& operator=(const ListIter& other) 
        {
            _ptr = other._ptr;
            return *this;
        }

        X& operator*() { return *dynamic_cast<T*>(_ptr); }
        X* operator->() { return dynamic_cast<T*>(_ptr); }
        ListIter& operator  () { _ptr = static_cast<T*>(_ptr->_next); return *this; }
        ListIter& operator--(){ _ptr = static_cast<T*>(_ptr->_prev); return *this; }
        ListIter operator  (int) { auto r(*this); operator  (); return r; }
        ListIter operator--(int){ auto r(*this); operator--(); return r; }
        difference_type operator-(const ListIter& other) {
            return (_ptr - other._ptr);
        }

        friend auto operator<=>(const ListIter& lhs, const ListIter& rhs)
        {
            if ((lhs._ptr - rhs._ptr) < 0)
                return std::strong_ordering::less;
            else if ((lhs._ptr - rhs._ptr) > 0)
                return std::strong_ordering::greater;
            return std::strong_ordering::equivalent;
        }

        friend bool operator==(const ListIter& lhs, const ListIter& rhs)
        {
            return (lhs <=> rhs) == 0;
        }
    };

    Link<T> _head;

public:
    using iterator = ListIter<T>;
    using const_iterator = ListIter<const T>;

    List() 
    {
        _head._next = &_head;
        _head._prev = &_head;
    }
    
    List(const List& other) // Problem here, does not work, not sure how to get this solved.
    {
for (auto ptr = other._head._next; ptr != &other._head; ptr = ptr->_next)
        {
            T* item = new T(*dynamic_cast<T*>(ptr)));

            Link<T>* current = &_head;
            Link<T>* previous = &_head;

            current->_next = item;
            previous = current;

            /*
            
            // link to new head
            _head._next = other._head._next;
            _head._prev = other._head._prev;

            // Link prev och next to correct head
            _head._next->_prev = &_head;
            _head._prev->_next = &_head;
            
            */
    }
    }
    
    List(const char* other)
    {
        for (size_t i = 0; i < strlen(other);   i)
            _head.insert_after(new T(other[i]));
    }

    ~List()
    {
        while (_head._next != &_head)
        {
            pop_front();  // This isn't efficient. 
        }
    }

    T* pop_front() 
    {
        return _head.erase_first();
    }
    
    T* pop_back() 
    {
        return _head.erase_last();
    }

    void push_front(T* node) { _head.insert_before(node);}
    void push_back(T* node) { _head.insert_after(node);}
};

CodePudding user response：

First off: I think the design here is a terrible idea; it looks like you're using the curiously recurring template pattern, but relying on dynamic_cast is pointless if so (the whole point is to get compile-time polymorphism, which means a static_cast from Link<T> to T (which is a child of Link<T>) should always be safe, and if it's not (because maybe your _head is a placeholder of type Link<T>, not an instance of T?), it's because you've written code that incorrectly treats them equivalently. I might suggest a refactor into three components:

T - the user's chosen type, which need not inherit from any given class, where currently your use of the curiously recurring template pattern requires it to inherit from Link<T>
Link<T> - The platonic ideal of a forward and reverse linked element of a linked list with no associated value (used solely for _head), where _prev and _next are pointers to Link<T> that, aside from pointers to _head, always point to Node<T>s.
Node<T> - A child class of Link<T> that adds a T data member and very little else (to avoid overhead, almost all behaviors not related to T itself would be defined non-virtually on Link<T>)

With the three of those, plus appropriate emplace* methods, you have the same features you currently have:

_head can be a plain Link<T> (no need to store a dummy T, nor require uses to define a default constructor)
All other elements are Node<T>, and have the same overhead of your current Link<T> (one instance of T plus two pointers)
T can be of arbitrary type (emplace* methods means the construction of a T can be deferred until the moment the Node<T> is created, no copies or moves of T needed)

where #3 is a stealth improvement which I'll repeat:

T can be of arbitrary type, not just subclasses of Link<T>

and you get the added benefit of:

Hiding more of your implementation (Link and Node can be private helper classes, where right now Link must be part of your public API), avoiding a lot of back-compat constraints that come with more of the API publicly visible

Secondly, your code is perfectly effective, it's just mildly inefficient (setting four pointers via indirection per new element, when you could set just two per element, and two more at the end to establish the List invariant). It's still a O(n) copy operation, not the O(n**2) operation a Schlemiel the Painter's algorithm would involve.

Beyond that, taking your word that everything else works, all you need to do to write a maximally efficient copy constructor is:

Begin with a pointer to the current element (_head), which I'll call current_tail (because at every stage of the copy, it's the logical tail of the list to date, and if no other element is found, it will be the real tail)
For each new element copied from other:
1. Set its _prev to current_tail (because current_tail is the current tail of the List, creating the reverse linkage)
2. Set current_tail's _next to the new element (creating the forward linkage)
3. Set current_tail to the new element (because now that they're linked to each other completely; we don't need a previous at all)
When you've copied everything per step 2, fix up the cycle, tying the final element to _head and vice-versa.

The end result is simpler than what you were writing (because you don't need a previous pointer at all):

List(const List& other) // Problem here, does not work, not sure how to get this solved.
{
    Link<T>* current_tail = &_head;   // 1. The tail of an empty list points to _head
    for (auto ptr = other._head._next; ptr != &other._head; ptr = ptr->_next)
    {
        T* item = new T(*dynamic_cast<T*>(ptr)));
        // We have validly forward linked list at each loop, so adding new element just means:
        item->_prev = current_tail ;  // 2.1. Telling it the prior tail comes before it
        current_tail->_next = item;   // 2.2. Telling the prior tail the new item comes after it
        current_tail = item;          // 2.3. Update notion of current tail
    }
    current_tail->_next = &_head;     // 3. Real tail's _next points to _head to indicate end of list
    _head._prev = current_tail;       // _head._prev is logical pointer to tail element, fix it up
    
}

You might need a couple casts sprinkled in there to deal the weirdness of List<T> also being T (and storing it with different types in different places), but otherwise that's it).

Voila, the only two uses of indirect variables per loop (both writes; all loads come from locals) rather than five (four written, one read; each reference to _prev is implicitly indirect use of this->_prev) involved when you push_back repeatedly.

For bonus points, write yourself a swap helper (using the copy-and-swap idiom), which really only needs to change four items (_head's _next and _prev to swap all the nodes of each List, the _next of the tail element, and the _prev of the current head element to point to the _head of the new owning List), and about six lines of simple boilerplate will get you a cheap, efficient and safe move constructor and assignment operator.