mercredi 13 avril 2022

Generic doubly linked list copy constructor efficiency and linkage

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.m_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);}
};

Aucun commentaire:

Enregistrer un commentaire