LinkedList复制构造函数实现细节

Question

我开始学习 C++，并作为练习决定实现一个简单的 LinkedList 类（下面是部分代码）。我有一个关于复制构造函数的实现方式以及访问原始 LinkedList 上数据的最佳方式的问题。

    template <typename T>
    class LinkedList {

        struct Node {
            T data;
            Node *next;

            Node(T t, Node *n) : data(t), next(n) {};
        };

    public:
        LinkedList();
        LinkedList(const LinkedList&);
        ~LinkedList();

        //member functions
        int size() const;              //done
        bool empty() const;            //done
        void append(const T&);         //done
        void prepend(const T&);        //done
        void insert(const T&, int i); 
        bool contains(const T&) const; //done
        bool removeOne(const T&);      //done
        int  removeAll(const T&);      //done
        void clear();                  //done
        T& last();                     //done
        const T& last() const;         //done
        T& first();                    //done
        const T& first() const;        //done
        void removeFirst();            //done
        T takeFirst();                 //done
        void removeLast();
        T takeLast();


        //delete when finished
        void print();                  
        //end delete

        //operators
        bool operator ==(const LinkedList<T> &other) const;    //done
        bool operator !=(const LinkedList<T> &other) const;    //done
        LinkedList<T>& operator =(const LinkedList<T> &other); //done


    private:
        Node* m_head;
        Node* m_tail;
        int   m_size;

    };

    template<typename T>
    LinkedList<T>::LinkedList() : m_head(0), m_tail(0), m_size(0) {

    }
...

我的复制构造函数是否应该直接访问原始 LinkedList 每个节点上的数据？

template<typename T>
LinkedList<T>::LinkedList(const LinkedList& l) {

    m_head = 0;
    m_tail = 0;
    m_size = 0;

    Node *n = l.m_head;

    // construct list from given list
    while(n) {
        append(n->data);
        n = n->next;
    }
}

或者我应该通过相应的访问器来访问数据？ （我知道我没有定义访问器）。

另外，我打算创建一个自定义迭代器，以便可以迭代LinkedList。我应该在复制构造函数中使用来访问每个节点上的数据吗？

另一个问题（我知道完全偏离主题），何时和/或为什么我们应该声明一个指向 LinkedList 的指针

LinkedList<int> *l = new LinkedList<int>(); 

而不是

LinkedList<int> l;

Answer 1

我认为追加将正确处理初始头/尾细节，是吗？如果是这样，那么您现在所拥有的就非常简单：浏览另一个列表，获取其项目并将副本添加到我的列表中。完美的。

嗯，差不多了。使用初始化列表来初始化成员变量：

template<typename T>
LinkedList<T>::LinkedList(const LinkedList& l) :
m_head(0), m_tail(0), m_size(0)
{
 // ...
}

另外，也许是风格问题，这可以代替 while 循环：

// construct list from given list
for (Node *n = l.m_head; n != 0; n = n->next)
    append(m->data);

事实上，我建议这样做。当你有迭代器时，你会做类似的事情：

for (const_iterator iter = l.begin(); iter != l.end(); ++iter)
    append(*iter);

它只是更好地遵循 for 循环的风格。 （初始化某事、检查某事、执行某事）。但对于迭代器来说，情况可能会有所不同。 （稍后详细介绍）

---

或者我应该通过相应的访问器来访问数据？ （我知道我没有定义访问器）。

此外，我打算创建一个自定义迭代器，以便可以迭代 LinkedList。我应该在复制构造函数中使用来访问每个节点上的数据吗？

这些迭代器是您的访问器。您不想暴露您的内部头尾指针，这会导致灾难。该类的目的是不暴露细节。也就是说，迭代器是这些细节的抽象包装器。

一旦有了迭代器，您就可以使用它们来迭代列表而不是指针算术。这与最近的有关提出问题。一般来说，您应该使用抽象来处理数据。所以是的，一旦你有了迭代器
在适当的位置，您应该使用它们来迭代数据。

大多数提供迭代器的类还提供了一种在给定开始和结束迭代器的情况下插入数据的方法。这通常称为insert，如下所示：insert(iterBegin, iterEnd)。这会循环遍历迭代器，将其数据附加到列表中。

如果您有这样的功能，您的复制构造函数将很简单：

insert(l.begin(), l.end()); // insert the other list's entire range

其中 insert 的实现就像我们上面的 for 循环一样。

---

另一个问题（完全偏离主题，我知道），何时和/或为什么我们应该声明一个指向 LinkedList 的指针

LinkedList *l = new LinkedList();而不是 LinkedList l；

第一个是动态分配，第二个是自动（堆栈）分配。您应该更喜欢堆栈分配。它几乎总是更快，也更安全（因为您不需要删除任何内容）。事实上，一个称为 RAII 的概念依赖于自动存储，因此保证析构函数能够运行。

仅在必要时才使用动态分配。

Answer 2

我认为实现自己的链表仍然是一个非常有价值的练习，因为它可以帮助您学习指针、数据结构等的详细信息。请确保不要在实际代码中使用链表类，因为有许多现有的库已经编写并测试过。最好的代码是您不必编写的代码。请参阅 std::list。

我认为您实现复制构造函数的方式没有问题。不过，您最好将代码移动到专用的复制函数并从构造函数中调用它，这样您需要维护的代码就会减少。但一般来说，从类本身内部使用类的实现细节不仅是可以接受的，而且在许多情况下是首选，因为它会尽可能快。

至于使用 new 创建列表与在堆栈上创建列表，这个决定不仅适用于您的类，而且适用于一般数据结构。过于简化的经验法则：如果可以的话在堆栈上分配，如果需要的话在堆上分配。例如，如果您需要列表比创建它的函数寿命更长，则需要这样做。

再次回到不手动滚动您自己的代码，如果您确实决定使用 new 在堆上分配，您应该使用智能指针，而不是尝试自己管理内存。现在就让自己养成这个习惯。不要等到你正在编写“真正的”代码。您遇到的许多人对您寻找编写更好的代码没有帮助，并且会坚持“只使用 new”。