c++ - 规则为 3 的 SinglyLinkedList 实现

Question

我是 C++ 的新手，一直在尝试实现一个单链表，它提供了析构函数、复制构造函数和赋值运算符的实现。我在尝试实现复制构造函数和赋值运算符时遇到了编译问题。

这是node.hpp

#ifndef LINKED_LIST_NODE_HPP
#define LINKED_LIST_NODE_HPP

template <typename T>
class Node{
public:
    T data;
    Node* next;
    Node();
    Node(T);
    Node(const Node&);
    ~Node();

};

template <typename T>
Node<T>::Node(){}

template <typename T>
Node<T>:: Node(const T data): data(data), next(nullptr){}

template <typename T>
Node<T>::Node(const Node<T>& source) : data(source.data),
                         next(new Node)
{
  (*next) = *(source.next) ;
}

template <typename T>
Node<T>::~Node(){}


#endif //LINKED_LIST_NODE_HPP

这是singly_linked_list.hpp

#ifndef LINKED_LIST_SINGLYLINKEDLIST_HPP
#define LINKED_LIST_SINGLYLINKEDLIST_HPP

#include <iostream>
#include "node.hpp"

template <typename T>
class SinglyLinkedList {

private:
    Node<T>* head;
    std::size_t count;

public:
    SinglyLinkedList();
    SinglyLinkedList(const SinglyLinkedList& source);
    SinglyLinkedList& operator=(const SinglyLinkedList& source);
    ~SinglyLinkedList();
    void insert(T);
    void remove(T);
    bool isEmpty();
    int length();
    void print();

};

template <typename T>
SinglyLinkedList<T>::SinglyLinkedList() : head(nullptr), count(0){}

template <typename T>
template <typename T>
SinglyLinkedList<T>::SinglyLinkedList(const SinglyLinkedList& source){

    Node<T>* curr = source.head;

    while(curr != nullptr){
        Node<T>* p = new Node<T>;
        p->data = curr->data;
        curr = curr->next;

    }

}

//template <typename T>
//SinglyLinkedList<T>::SinglyLinkedList& operator=(const SinglyLinkedList<T>& source){
//    //not sure how to implment this.
//}

template <typename T>
SinglyLinkedList<T>::~SinglyLinkedList() {
    if(!isEmpty()){
        Node<T>* temp = head;
        Node<T>* prev = nullptr;
        while(temp->next != nullptr){
            prev = temp;
            temp = temp->next;
            delete prev;
        }
        delete temp;
    }
}

template <typename T>
bool SinglyLinkedList<T>::isEmpty() {
    return head == nullptr;
}

template <typename T>
void SinglyLinkedList<T>::insert(T item) {
    Node<T>* p = new Node<T>(item);
    p->next = head;
    head = p;
    count += 1;

}

template <typename T>
void SinglyLinkedList<T>::remove(T item) {
    bool present = false;
    if (head->data == item){
        Node<T>* temp = head;
        head = head->next;
        delete(temp);
        count -= 1;
        return;
    }
    Node<T>* temp = head;
    while (temp->next != nullptr){
        if (temp->next->data == item){
            Node<T>* removable = temp->next;
            temp->next = temp->next->next;
            delete(removable);
            present = true;
            count -= 1;
            break;
        } else{
            temp = temp->next;
        }
    }
    if(!present){
        throw std::invalid_argument("item not present in list");
    }
}

template <typename T>
int SinglyLinkedList<T>::length() {
    return count;
}

template <typename T>
void SinglyLinkedList<T>::print() {
    if(isEmpty()){
        throw std::invalid_argument("Can't print an empty list!");
    }
    Node<T>* temp = head;
    while(temp != nullptr){
        if(temp->next != nullptr){
            std::cout<<temp->data;
            std::cout<<"->";
        }else{
            std::cout<<temp->data;
        }
        temp = temp->next;
    }
    std::cout<<std::endl;

}

#endif //LINKED_LIST_SINGLYLINKEDLIST_HPP

我已经注释掉了复制构造函数代码以进行编译。这样做的正确方法是什么？我正在学习 C++。

Answer 1

引入复杂性的一个问题是没有明确定义节点的复制构造函数应该做什么？拷贝的 next 字段应该指向原件的下一个，还是应该创建下一个的拷贝并指向那个？前者不充分且容易出错，后者会递归地创建整个列表的拷贝，一次一个节点。这适用于小列表，但由于递归调用的深度，将导致包含许多元素的列表的堆栈溢出。

所以为了简单起见，我不会为节点的复制构造函数而烦恼。

template <typename T>
class Node {
public:
    T data;
    Node* next = nullptr;

    Node() = default;
    Node(const Node&) = delete; // since copying is not well defined, make it impossible to copy a node.
};

复制列表是一个定义明确的操作，因此实现复制构造函数是有意义的。当前实现的一个错误是您分配了一个新节点，只是在以后泄漏它(没有任何东西跟踪新分配的节点 p)。您需要的看起来更像这样:

template <typename T>
SinglyLinkedList<T>::SinglyLinkedList(const SinglyLinkedList<T>& source)
    : head(nullptr)
    , count(0)
{
    // deal with the trivial case of empty list
    if (source.head == nullptr)
        return;

    // deal with the case where count >= 1
    head = new Node<T>;
    head->data = source.head->data;
    head->next = nullptr;
    count = 1;

    Node<T>* lastCopied = source.head;  // last node to be copied
    Node<T>* lastAdded = head;         // last node to be added to the current list
    while (lastCopied->next != nullptr)
    {
        // create new node
        Node<T>* p = new Node<T>;
        p->data = lastCopied->next->data;
        p->next = nullptr;

        // link the newly created node to the last of the current list
        lastAdded->next = p;
        lastAdded = p;

        // advance lastCopied
        lastCopied = lastCopied->next;
        count++;
    }
}

现在关于赋值运算符，幸运的是您可以使用大大简化事情的“ copy-and-swap ”习惯用法。

template <typename T>
SinglyLinkedList<T>& SinglyLinkedList<T>::operator =(SinglyLinkedList<T> source)  // note that you pass by value.
{
    std::swap(head, source.head);
    std::swap(count, source.count);
    return *this;
}

如果我试图解释 copy-and-swap 技术，我的回答会变得太长。编写异常安全代码并同时避免重复(通过使用复制构造函数实现赋值)是一个聪明的技巧。值得一读here .

顺便说一下，你的类的声明应该是这样的

template <typename T>
class SinglyLinkedList 
{

private:
    Node<T>* head = nullptr;
    std::size_t count = 0;

public:
    SinglyLinkedList(const SinglyLinkedList& source);
    SinglyLinkedList& operator=(SinglyLinkedList source);
    // other members here...
};

附言。我的代码假定您使用的是 c++11 或更高版本的标准。