5

我开始学习 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;
4

2 回答 2

3

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

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

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

Whereinsert的实现就像我们上面的 for 循环一样。

另一个问题（完全题外话，我知道），我们何时和/或为什么要声明指向 LinkedList 的指针

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

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

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

于 2010-03-03T19:50:19.927 回答
0

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

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

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

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

于 2010-03-03T19:55:59.510 回答