模版双链表

Question

我一直想修改我所知道的关于模板类的内容，所以我想写一个双链接的列表来练习。

一切都很好，所以在这方面一切都很好，但是有什么我错过了吗？

我现在知道的事情：

• 命名-可以更明确一点
• 功能--即处理节点*指针，这样我就可以(例如)搜索和删除包含某个值的节点，而无需对列表进行两次扫描。

我计划以后再修正/增加这个问题。

具体来说，我主要是寻找关于我是如何做模板的反馈，以及任何RAII问题，尽管我很乐意接受任何进一步的反馈。

请注意，我使用.h作为接口头，并使用.hpp作为实现来分隔接口和实现(使用.hpp而不是.imp或类似于系统上识别的类型)。我理解模板要对所有类型都有效，它需要在头中，否则需要定义要使用的每个类型，对吗？

我一直在编辑：

g++ -std=c++11 use_dllist.cpp -Wall -Wextra -pedantic -o dll.exe

dlllist.h:

#ifndef __d_l_list__
#define __d_l_list__
#include <string>
template<class T>class d_l_listnode
{
public:
   d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
   T data;
};

template<class T> class d_l_list
{
    d_l_listnode<T>* end[2] = {0,0};  //end[0] is head end[1] is tail
    int node_count = 0;

    void deep_copy(d_l_list<T>& original,d_l_list<T>& destination);

public:
    d_l_list();
    d_l_list(d_l_list<T>&);
    d_l_list<T>& operator=(d_l_list<T>&);
    ~d_l_list();
    int  add_node(T data, int index);
    int  find_node(T data);
    bool del_node(int index);
    bool is_empty();
    int  get_node_count();
    void print_list(std::string delimiter);
    void print_list_debug();
};

#include "dllist.hpp"
#endif

dllist.hpp:

#include <iostream>

template<class T>
d_l_list<T>::d_l_list()
{
    node_count = 0;
    end[0] = NULL;
    end[1] = NULL;
}

template<class T>
void d_l_list<T>::deep_copy(d_l_list<T>& original, d_l_list<T>& destination)
{
  destination.node_count = 0;
  destination.end[0] = NULL;
  destination.end[1] = NULL;
  d_l_listnode<T>*current_node = original.end[1];
  while(current_node)
  {
    destination.add_node(current_node->data, 0);
    current_node = current_node->link[0];
  }
}

template<class T>
d_l_list<T>::d_l_list(d_l_list<T>& original)
{
  deep_copy(original, *this);
}

template<class T>
d_l_list<T>& d_l_list<T>::operator=(d_l_list<T>& original)
{
  deep_copy(original, *this);
  return *this;
}

template<class T>
d_l_list<T>::~d_l_list()
{    while(node_count){del_node(0);}}

template<class T>
void d_l_list<T>::print_list(std::string delimiter)
{
  d_l_listnode<T>* node = end[0];
  while(node)
  {
    std::cout << node->data << (node->link[1]?delimiter:"");
    node = node->link[1];
  }
  std::cout<<std::endl;
}

template<class T>
void d_l_list<T>::print_list_debug()
{
  std::cout<<"head: "<<end[0]<<":"<<(node_count?end[0]->link[0]:0)<<"\ntail: "<<end[1]<<":"<<(node_count?end[1]->link[1]:0)<<std::endl; //second should always print '0'. If not, problem.
  d_l_listnode<T>* node = end[0];
  while(node)
  {
    std::cout<<node->data<<"\t\t:"<<node<<"\t"<<node->link[0]<<"\t:"<<node->link[1]<<"\n";
    node = node->link[1];
  }
  std::cout<<std::endl;
}

template<class T>
int d_l_list<T>::get_node_count()
{
  return node_count;
}

template<class T>
int d_l_list<T>::find_node(T data)
{
  int index = 0;
  d_l_listnode<T>* current_node = end[0];
  while (current_node)
  {
    if (current_node->data == data)
      return index;
    current_node = current_node->link[1];
    index++;
  }
  return -1;
}

template<class T>
int d_l_list<T>::add_node(T data, int index)
{
  bool traversal_direction = true;

  if (index > node_count/2){
    index = node_count - index;
    traversal_direction = false;}

  if (index < 0)
    {index = 0;}

  d_l_listnode<T>* new_node = new d_l_listnode<T>;
  if (!new_node)
    {return -1;}

  new_node->data=data;

  if (!end[0])
  {
    end[0] = new_node;
    end[1] = new_node;
    node_count = 1;
    return 0;
  }

  d_l_listnode<T>* current_node = end[!traversal_direction];

  for (int i = 0; i < index && i < node_count; i++)
    {current_node = current_node->link[traversal_direction];}

  if (!(current_node->link[0]&¤t_node->link[1]))
  {
    end[!traversal_direction] = new_node;
    new_node->link[!traversal_direction] = NULL;
  }
  else
  {
    new_node->link[!traversal_direction] = current_node->link[!traversal_direction];
    new_node->link[!traversal_direction]->link[traversal_direction] = new_node;
  }
  new_node->link[traversal_direction] = current_node;
  current_node->link[!traversal_direction] = new_node;

  node_count++;
  return traversal_direction?index:node_count-index-1;
}

template<class T>
bool d_l_list<T>::del_node(int index)
{
  if (!node_count) 
    {return false;}

  bool traversal_direction = true;

    if (index >= node_count/2)
    {
      index = node_count - index - 1;
      traversal_direction = false;
    }

    d_l_listnode<T>* current_node = end[!traversal_direction];

    if (index < 0)
      {index = 0;}

    for (int i = 0; i < index; i++)
      {current_node = current_node->link[traversal_direction];}

    for (int i = 0; i <= 1; i++)
    {
      if (!current_node->link[!i])
        {end[!i] = current_node->link[i];}
      else
        {current_node->link[!i]->link[i] = current_node->link[i];}
    }
  //}
  delete current_node;
  node_count--;
  return true;
}

use_dllist.cpp (只是用来行使功能的东西)：

#include "dllist.h"
#include <iostream>
#include <climits>


void printout(d_l_list<int>& list)
{
    std::cout << "\nnumber of nodes: " << list.get_node_count() << std::endl;
    std::cout << "list contents:" << std::endl;
    list.print_list(", ");
}

int main()
{
    d_l_list<int> list;

    std::cout<<"created list" << std::endl;

    //printout(list);

    for (int i = 0; i<10; i++)
    {
        int j = list.add_node(i, 5);
        std::cout<<"added a node, value: "<<i<<", index: "<< j << std::endl;
    }

    printout(list);

    {
      std::cout<<"\nCopy Constructor:"<<std::endl;
      d_l_list<int> list2(list);
      printout(list2);
    }
    {
      std::cout<<"\nAssignment:"<<std::endl;
      d_l_list<int> list3 = list;
      printout(list3);
    }

    std::cout<<"\nfinding '8'" << std::endl;
    int index = list.find_node(8);
    std::cout<<"deleting '8' (index: "<<index<<")"<< std::endl;

    list.del_node(index);

    printout(list);

    std::cout<<"\ndeleting #1" << std::endl;
    list.del_node(1);

    printout(list);

    std::cout<<"\ndeleting #5" << std::endl;
    list.del_node(5);

    printout(list);

    std::cout<<"\ndeleting #INT_MAX ("<<INT_MAX<<")" << std::endl;
    list.del_node(INT_MAX);

    printout(list);

    while(list.get_node_count())
    {
      std::cout<<"\ndeleting #0" << std::endl;
      list.del_node(0);
      printout(list);
    }
}

Answer 1

文件扩展名

将接口与实现分离是很好的。然而，.h/..hpp的分裂并不明显。用于无法进入.cpp文件的实现文件的最常见的文件扩展名是.inl (用于inline)和.tpp (用于template cpp)。我知道至少有一些代码编辑器或IDE识别扩展.inl (至少代码：：块)，但其中许多代码编辑器或IDE仍然可以被配置为识别其他扩展。尝试在实现文件中使用更明显的东西，即.hpp。

名称

关于一般姓名的几点评论：

• 尝试用FULL_CAPS_CASE编写预处理器名称，以便只需一眼就可以识别它们，而不会与常规函数、类或变量名称混淆。
• 此外，您的头保护名称是不正确的:带有双下划线的名称(名称中的任何位置)都是为实现者保留的。以下划线开头、大写字母后面的名称也是为实施者保留。一个好的格式良好的名称为您的标题守卫将是D_L_LIST_，因为单一的尾随下划线是好的。
• 如果可能，尝试在cass模板中使用注入类名。它允许编写更短的代码并减少维护成本:如果更改模板参数名称，就不必编辑使用注入类名的行。例如，您的operator=将变成: d_l_list& operator=(d_l_list&)；
• print_list是方法的坏名称，因为您已经知道正在打印list。一个更好的名字可能是print，但我们稍后会看到一种更惯用的打印方法。

const-correctness

您应该真正考虑到const-correctness，这意味着您应该添加const来指定对象不会被修改：

• operator=应该使用一个const d_l_list&而不是一个d_l_list&来断言它不会修改指定的变量。
• 所有不修改类的方法都应该标记为const：bool is_empty() const；还有许多这样的方法：print_list、print_list_debug、get_node_count、is_empty和find_node。

印刷品

在C++中打印内容的惯用方法是为std::ostream&和您的类型重载operator<<。就你而言，应该是：

template<typename T>
std::ostream& operator<<(std::ostream& stream, const d_l_list<T>& list)
{
    // print stuff to stream...
    return stream;
}

注意，重载运算符是一个空闲函数，而不是类方法。

空指针常数

目前，您正在使用两种不同的方法来表示空指针常量：

• NULL，和end[0] = NULL;一样。
• 0和d_l_listnode* link[2] = {0,0};一样。

您正在使用C++11，表示空指针常量的C++11方法是nullptr。上述两行可改写为：

• end[0] = nullptr;
• d_l_listnode* link[2] = {nullptr,nullptr};。

类内初始化器和默认构造

您使用类内初始化器默认初始化d_l_list的成员.但是，您可以在默认构造函数中使用完全相同的值初始化它们。实际上，如果您使用显式默认的默认构造函数，它将使用类内初始化器来初始化成员。因此，您可以简单地将其定义为：

template<class T>
d_l_list<T>::d_l_list()
    = default;

使用复制和交换成语

抄袭互换成语是一种成语，它可以让你写出正确而简短的代码。简而言之，拷贝应该写在类的复制构造函数中，而operator=应该依赖复制构造函数来执行副本。下面是你的班级的样子：

template<class T>
d_l_list<T>::d_l_list(const d_l_list<T>& other)
{
  // Uninitialized members use the
  // in-class initializers here, that's
  // why I left out the initialization part

  d_l_listnode<T>* current_node = other.end[1];
  while(current_node)
  {
    this->add_node(current_node->data, 0);
    current_node = current_node->link[0];
  }
}

template<class T>
d_l_list<T>& d_l_list<T>::operator=(d_l_list<T> other)
{
  swap(*this, other);
  return *this;
}

简而言之，operator=通过复制构造函数执行other的副本，然后交换*this和other的内容。然后，对other进行销毁，清洗其内容(*this的原始内容)。我所链接的那篇文章进一步深入了细节，非常值得一读。无论如何，使用复制和交换成语是安全的，有效的，并允许您删除deep_copy方法。

Answer 2

几个注意事项：

你有这样的代码：

d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
[...]
d_l_listnode<T>* end[2] = {0,0};  //end[0] is head end[1] is tail

和客户代码：

destination.end[0] = NULL;

在客户端代码中(也就是说，您需要知道这一点)，您不需要查看类声明，就无法清楚地知道0的意思是尾向的。

您可以定义一个枚举，这样就可以拥有：

destination.end[left_link] = NULL;
destination.end[right_link] = NULL;

这将确保客户端代码的一致性和语义信息的改进。

考虑实现与STL兼容的迭代访问。这将使您能够以许多惯用的方式使用该类(比如对流输入和输出以及std算法执行迭代操作:例如查找和排序)。

考虑使用类的全名(d_l_list使我出于某种原因想到了一个“下载列表”)。另外，请考虑调用类bidi_list (或类似的东西)：它为迭代和插入提供了快速访问，这在客户端代码中很重要；它作为链接列表实现的事实只是实现细节。