c++ - 为什么链表中的节点不能负责删除自己？ (C++)

Question

我的想法是，一旦第一个节点从链表类中删除，其余节点就会随之删除。我的实现在实践中不起作用。是否有逐个节点删除整个列表而不是删除所有链表的解决方案？我的 nodeT 应该有析构函数吗？

链表实现:

#include <iostream>
#include <cassert>
#include "nodeT.h"
class linkedListSort
{
public:
    int print();
      //Function to output the elements of the list
      //Postcondition: Elements of the list are output on the 
      //   standard output device. Member current is reset to beginning node
      //   and currentIndex is reset to 0
      //Returns:  number of items printed in the list
      //          also outputs error if number of items printed
      //          does not equal the length of the list

    void insertAt(int location, elemType& insertItem);
      //Function to insert an item in the list at the 
      //position specified by location. The item to be inserted 
      //is passed as a parameter to the function.
      //Postcondition: Starting at location, the elements of the
      //    list are shifted down, list[location] = insertItem;,
      //    and length++;. If the list is full or location is
      //    out of range, an appropriate message is displayed.

      linkedListSort(int size = 100);

      ~linkedListSort();

protected:
  //consider making const
  nodeT<elemType> *beginningNode;  // handle to the beginning of the list
  nodeT<elemType> *current;  // pointer to current node
  int currentIndex;  //int representing which node in the list current is pointing to
  int length;      //to store the length of the list
  int maxSize;     //to store the maximum size of the list

  };

template <class elemType>
linkedListSort<elemType>::linkedListSort(int size)
{
  if (size < 0)
  {
    cerr << "The array size must be positive. Creating "
      << "an array of size 100. " << endl;

    maxSize = 100;
  }
  else
    maxSize = size;

  beginningNode = NULL;
  current = NULL; // initialize to empty linked list
  length = 0;
  currentIndex = -1; // there is no item that current points to
}

template <class elemType>
linkedListSort<elemType>::~linkedListSort()
{
  delete beginningNode;  // this should delete all linked list items ( see nodeT destructor )
}

链表节点实现:

template <class elemType>
class nodeT {
public:
  nodeT(elemType& infoParam, nodeT<elemType> *linkParam);  //standard
  nodeT(elemType& infoParam);  //if unlinked node (ex. last item)
  nodeT();
  //copy constructor
  nodeT(nodeT<elemType>& node);
  ~nodeT();
  elemType *info;
  nodeT *link;
};

template<class elemType>
nodeT<elemType>::nodeT(elemType& infoParam, nodeT<elemType> *linkParam) {
  info = &infoParam;
  link = linkParam;
}

//when link is null (last item and uncircular)
template<class elemType>
nodeT<elemType>::nodeT(elemType& infoParam) {
  info = &infoParam;
  link = NULL;
}

//in case node is needed before info or link is known (default)
template<class elemType>
nodeT<elemType>::nodeT() {
  info = NULL;
  link = NULL;
}

template<class elemType>
nodeT<elemType>::nodeT(nodeT<elemType>& node) {
  info = new elemType();
  if (node.link != NULL)
    link = new nodeT();

  *info = *(node.info);  // copy by value
  if (node.link != NULL)
    *link = *(node.link);
  else
    link = NULL;
}

template<class elemType>
nodeT<elemType>::~nodeT() {
  delete info;
  if (link != NULL)
    delete link;
}

节点实现的最后一部分是节点析构函数。如果 nodeT 链接的成员是 nodeT 类型，那么代码 delete link 将调用相同的析构函数，但只是在另一个实例上。因此，一旦第一个节点被销毁，每个节点都应该销毁自己。第一个节点在链表实现中被销毁，如下所示:delete beginningNode 其中 beginningNode 始终指向链表中的第一个节点。

我接近解决方案了吗？还是我只是掉进了 C++ 不想让你掉下去的兔子洞？

实际错误与断言失败有关。然后最终我可以将其复制到我的剪贴板:“chap10Ex1.exe 中 0x553056E8 (msvcr120d.dll) 处未处理的异常:0xC0000005:访问冲突读取位置 0x00000002。”

Answer 1

从技术上讲，您的节点不负责删除它们自己，它们负责删除列表中的下一个节点。

这看起来很有吸引力，但这里有一些您可能没有考虑过的含义。首先，@WhozCraig 在评论中说，您最终将为一个大列表构建相当深的析构函数调用堆栈。

其次，如果您成功地为自己构建了一个循环链接链，您将一直围绕它，然后在您第二次尝试删除第一个节点时遇到未定义的行为。您的代码中没有任何东西可以防止这种滥用 - 这些类型的保证是为列表使用容器类的优势之一，它向客户端隐藏了节点本身的操作。

我认为这里还有一个关于所有权的问题。节点不相互分配，但它们负责相互删除，这意味着每个节点拥有列表中的下一个节点。从您提供的 API 来看，这可能并不明显，它需要列表的用户创建新节点，但是当您将它们添加到列表时，列表会负责删除它们。这意味着在客户端代码中，new 之间没有平衡。和 delete ，这看起来有点奇怪。

然而，在所有权方面更糟糕的是列表节点析构函数调用 delete info ，它是在其中一个构造函数中创建的，作为传递的引用的地址，其中甚至可能不在堆上。你不能说，没有人在那里做出任何 promise 。至少您需要接受一个指针而不是一个引用，因为这暗示着正在发生所有权转移。更好的办法是接受 std::unique_ptr<elemType> ，这使得所有权的转移非常明确(您仍然可以通过原始指针提供对内容的访问)。

一般来说，我会建议，如果一个数据结构要负责删除某些内容，那么该数据结构也应该负责创建它。否则，你应该别管它。 STL 容器不会删除包含的指针 - 如果您删除 std::vector<int *>你必须删除所有 int *成员(member)自己先。这为用户提供了灵 active - 他们不必存储指向堆上事物的指针 - 这意味着它是一致的 - 那些负责创建某些东西的人通常也应该负责处理它。这也意味着 std::list<T>可以包含任何 T - 包括指针。如果您尝试实例化 nodeT<int *> 会发生什么？当它的析构函数运行时会发生什么？

所以我想说如果你要让节点互相删除你也应该让节点互相创建(并且不要让用户这样做)。如果您要让节点删除它们的数据项，您绝对应该也创建这些数据项。或者更好的是，让它单独存在并且不要触及通过引用传递给您的某些东西的生命周期。