C++模板 - LinkedList

Question

编辑 - 下面回答,错过了斜角的大括号.谢谢大家.

我一直试图写一个简单的单链表,我可以在其他程序中使用.我希望它能够使用内置和用户定义的类型,这意味着它必须是模板化的.

由于这个原因,我的节点也必须模板化,因为我不知道它将要存储的信息.我写了一个节点类如下 -

template <class T> class Node
{
    T data; //the object information
    Node* next; //pointer to the next node element

public:
    //Methods omitted for brevity
};

我的链表类是在一个单独的类中实现的,并且在将新节点添加到列表末尾时需要实例化一个节点.我已经实现了如下 -

#include <iostream>
#include "Node.h"
using namespace std;

template <class T> class CustomLinkedList
{
    Node<T> *head, *tail;

public:

    CustomLinkedList()
    {
        head = NULL;
        tail = NULL;
    }

    ~CustomLinkedList()
    {

    }

    //Method adds info to the end of the list
    void add(T info)
    {
        if(head == NULL) //if our list is currently empty
        {
            head = new Node<T>; //Create new node of type T
            head->setData(info);
            tail = head;
        }
        else //if not empty add to the end and move the tail
        {
            Node* temp = new Node<T>;
            temp->setData(info);
            temp->setNextNull();
            tail->setNext(temp);
            tail = tail->getNext();
        }
    }

    //print method omitted
};

我已经设置了一个驱动程序/测试类,如下所示 -

#include "CustomLinkedList.h"
using namespace std;

int main()
{
    CustomLinkedList<int> firstList;

    firstList.add(32);
    firstList.printlist();
    //Pause the program until input is received
    int i;
    cin >> i;

    return 0;
}

我在编译时遇到错误 - 错误C2955:'Node':使用类模板需要模板参数列表 - 这使我在add方法中指向以下代码行 -

Node* temp = new Node<T>;

我不明白为什么它没有关于类型的信息,因为它在我的驱动程序类中创建时被传递到链表.我应该怎么做才能将类型信息传递给Node？

我应该创建一个私有节点结构而不是一个单独的类,并将两个类的方法组合在一个文件中吗？我不确定这会克服这个问题,但我认为可能会这样.如果可能的话,我宁愿有单独的课程.

谢谢,安德鲁.

Answer 1

虽然答案已经提供,但我想我会添加我的盐.

在设计模板类时,最好不要在任何地方重复模板参数,以防万一您希望(有一天)更改特定细节.通常,这是通过使用typedef完成的.

template <class T>
class Node
{
public:
  // bunch of types
  typedef T value_type;
  typedef T& reference_type;
  typedef T const& const_reference_type;
  typedef T* pointer_type;
  typedef T const* const_pointer_type;

  // From now on, T should never appear
private:
  value_type m_value;
  Node* m_next;
};


template <class T>
class List
{
  // private, no need to expose implementation
  typedef Node<T> node_type;

  // From now on, T should never appear
  typedef node_type* node_pointer;

public:
  typedef typename node_type::value_type value_type;
  typedef typename node_type::reference_type reference_type;
  typedef typename node_type::const_reference_type const_reference_type;
  // ...

  void add(value_type info);

private:
  node_pointer m_head, m_tail;
};

最好在类声明之外定义方法,使其更容易读取接口.

template <class T>
void List<T>::add(value_type info)
{
  if(head == NULL) //if our list is currently empty
  {
    head = new node_type;
    head->setData(info);
    tail = head;
  }
  else //if not empty add to the end and move the tail
  {
    Node* temp = new node_type;
    temp->setData(info);
    temp->setNextNull();
    tail->setNext(temp);
    tail = tail->getNext();
  }
}

现在,几点评论:

• 如果List<T>::add将迭代器返回给新添加的对象,就像insertSTL中的方法一样(并且你可以重命名它也是如此),这将更加用户友好
• 在执行List<T>::add你分配内存temp然后执行一堆操作,如果有任何抛出,你已经泄露了内存
• 该setNextNull呼叫不应是必要的:的构造函数Node应该初始化所有数据成员meaningfull值,包括m_next

所以这是修订版:

template <class T>
Node<T>::Node(value_type info): m_value(info), m_next(NULL) {}

template <class T>
typename List<T>::iterator insert(value_type info)
{
  if (m_head == NULL)
  {
    m_head = new node_type(info);
    m_tail = m_head;
    return iterator(m_tail);
  }
  else
  {
    m_tail.setNext(new node_type(info));
    node_pointer temp = m_tail;
    m_tail = temp.getNext();
    return iterator(temp);
  }
}

注意使用正确构造函数的简单事实如何提高我们的异常安全性:如果在构造函数期间抛出任何东西,new则需要不分配任何内存,因此没有泄漏任何内容,我们还没有执行任何操作.我们的List<T>::insert方法现在很有弹性.

最后的问题:

insert单个链接列表的常用方法在开头插入,因为它更容易:

template <class T>
typename List<T>::iterator insert(value_type info)
{
  m_head = new node_type(info, m_head); // if this throws, m_head is left unmodified
  return iterator(m_head);
}

你确定要在最后使用插页吗？或者你是这样做的,因为push_back传统的矢量和列表的方法？

Answer 2

可能想试试

Node<T>* temp = new Node<T>;

另外,要获得有关如何设计列表的提示,您当然可以查看std :: list,尽管有时候它可能有点令人生畏.