在链表中移动和复制构造函数

Question

我仍在尝试了解有关复制和移动构造函数的更多信息。我有一个链接列表 class，我想使用复制和移动构造函数进行深度复制，但我遇到了问题。首先，为了深拷贝Listclass，我是不是只在构造函数中拷贝head_ and tail_。我知道代码很可怕，也许我不应该马上跳进高级的东西。

感谢任何帮助！

template<typename T>
class List
{
public:

    class Node {
    public:
        Node(T value) : value_(value) {}

        T value_;
        Node* next_;
        Node* prev_;
    };

    Node* head_;
    Node* tail_;


    //! Default constructor
    List() :tail_(nullptr) {}

    //! Copy constructor
    List(const List& lst) : head_(nullptr) {

        //not sure what goes in here
        }
    }

    //! Move constructor
    List(List&& move) {
        head_ = move.head_;
        move.head_ = nullptr;
        tail_ = move.tail_;
        move.tail_ = nullptr;
    }


//! Copy assignment operator
    List& operator= (const List& list) {
        
        tail_ = nullptr;
        head_ = tail_;
    
        Node* current = list.head_;
        Node* next = list.head_->next_;
        Node* replace = head_;
        while (next != list.tail_) {
            current = current->next_;
            next = next->next_;
            replace->next_ = tail_;
            replace->next_->value_;
            replace = replace->next_;
        }
        return *this;
    }
    

    //! Move assignment operator
    List& operator= (List&& other) {        
        
        tail_ = nullptr;
        head_ = tail_;

        head_->next_ = other.head_->next_;
        Node* current = other.head_;
        Node* next = other.head_->next_;

        while (next != other.tail_) {

            current = current->next_;
            next = next->next_;
        }
        current->next_ = tail_;
        other.head_->next_ = other.tail_;

        return *this;
    }

Answer 1

因为 List 跟踪尾部，您可以调用将项目添加到列表末尾的函数，而不会增加迭代到列表末尾的开销。

List(const List& lst) : head_(nullptr), tail_(nullptr) 
{
    Node * cur = lst.head_; //get first source item.
    while (cur) // if there is a source item to copy
    {
        push_back(cur->value_); // stick the item on the end of this list
        cur = cur->next_; // get next source item
    }
}

其中 push_back 看起来像

void push_back(T value)
{
    Node * newnode = new Node(value, tail_, nullptr); //make and link new tail node

    if (tail_)
    {
        tail_->next_ = newnode; // link in new node
    }
    else
    {
         head_ = newnode;
    }
    tail_ = newnode; // update tail
}

和Node选择了一个新的构造函数来简化插入：

Node(T value, 
     Node * prev, 
     Node * next) : value_(value), prev_(prev), next_(next) 
{
}

注意：在赋值运算符中，

tail_ = nullptr;
head_ = tail_;

切断指向链表中任何数据的指针，泄漏那些节点。在替换它们之前，您需要释放这些节点。 Copy and Swap Idiom (What is the copy-and-swap idiom?) 通过使用局部变量的复制构造和销毁来自动执行该过程，从而使这变得容易。

Answer 2

这是我的五分钱。:)

下面的演示程序展示了如何实现复制构造函数、移动构造函数、复制赋值运算符、移动赋值运算符和析构函数，包括一些其他辅助函数。

#include <iostream>
#include <utility>
#include <functional>
#include <iterator>

template<typename T>
class List
{
private:
    struct Node 
    {
        T value;
        Node *prev;
        Node *next;
    } *head = nullptr, *tail = nullptr;

    void copy( const List &list )
    {
        if ( list.head )
        {
            head = tail = new Node { list.head->value, nullptr, nullptr };

            for ( Node *current = list.head->next; current; current = current->next )
            {
                tail = tail->next = new Node { current->value, tail, nullptr };             
            }
        }           
    }
    
public:
    //! Default constructor
    List() = default;

    //! Copy constructor
    List( const List &list )
    {
        copy( list );
    }

    //  Constructor with iterators
    template <typename InputIterator>
    List( InputIterator first, InputIterator last )
    {
        if ( first != last )
        {
            head = tail = new Node { *first, nullptr, nullptr };

            while ( ++first != last )
            {
                tail = tail->next = new Node { *first, tail, nullptr };             
            }
        }
    }

    //  Destructor
    ~List()
    {
        clear();
    }
    
    //! Move constructor
    List( List &&list ) 
    {
        std::swap( head, list.head );
        std::swap( tail, list.tail );
    }

    //! Copy assignment operator
    List & operator =( const List &list ) 
    {
        clear();
        copy( list );
        
        return *this;
    }
    
    //! Move assignment operator
    List & operator =( List &&list ) 
    {
        std::swap( head, list.head );
        std::swap( tail, list.tail );
        
        return *this;
    }
    
    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }
        
        tail = head;
    }
    
    void push_front( const T &value )
    {
        head = new Node{ value, nullptr, head };

        if ( !tail )
        {
            tail = head;
        }
        else
        {
            head->next->prev = head;
        }
    }

    void push_back( const T &value )
    {
        Node *new_node = new Node{ value, tail, nullptr };

        if ( tail )
        {
            tail = tail->next = new_node;
        }
        else
        {
            head = tail = new_node;
        }
    }
    
    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current; current = current->next )
        {
            os << current->value << " -> ";
        }
        
        return os << "null";
    }
};

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    List<int> list1( std::begin( a ), std::end( a ) );
    
    std::cout << list1 << '\n';
    
    list1 = List<int>( std::rbegin( a ), std::rend( a ) );

    std::cout << list1 << '\n';
    
}

程序输出为

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null

比如在这个语句中

list1 = List<int>( std::rbegin( a ), std::rend( a ) );

使用了移动赋值运算符。

在链表中移动和复制构造函数

Move and copy constructors in a linked list

c++

copy-constructor

doubly-linked-list

class-design

move-constructor