c++ - 链表复制构造函数实现细节

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;
    }
}

还是应该通过相应的accessor访问数据？ (我知道我没有定义访问器)。

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

另一个问题(我知道这完全是题外话)，什么时候和/或为什么我们应该声明一个指向 LinkedList 的指针

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

代替

LinkedList<int> l;

Answer 1

我假设 append 会正确处理初始的头部/尾部细节，是吗？如果是这样，那么您现在拥有的东西非常简单:浏览另一个列表，取出它的项目并将拷贝添加到我的列表中。完美。

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

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

另外，也许是风格问题，这个 wok 而不是 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 循环的风格。 (初始化某事，检查某事，做某事)。尽管对于迭代器，它可能会有所不同。 (稍后更多)

---

Or should I access the data through the corresponding accessor? (I know that I don't have the accessor(s) defined).

Also, I intend to create a custom iterator so that it can be possible to iterate over the LinkedList. Should I use in the copy constructor to access the data on each node?

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

一旦有了迭代器，就可以使用它们来遍历列表而不是指针运算。这与最近有关 asked question .通常，您应该使用您的抽象来处理您的数据。所以是的，一旦你有了迭代器到位后，您应该使用它们来遍历数据。

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

如果您有这样的功能，您的复制构造函数将只是:

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

insert 的实现类似于我们上面的 for 循环。

---

Another question (completely off-topic, I know), when and/or why should we declare a pointer to a LinkedList

LinkedList *l = new LinkedList(); instead of LinkedList l;

第一个是动态分配，第二个是自动(栈)分配。您应该更喜欢堆栈分配。它几乎总是更快，也更安全(因为您不需要删除任何东西)。事实上，一个叫做 RAII 的概念依赖于自动存储，因此析构函数可以保证运行。

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