3

我对实现一个双向链表有点困惑，其中列表中的数据是指针。

我的链表类的私有部分如下所示：

 private:
    struct node {
      node* next;
      node* prev;
      T* o;
    };
    node* first; // The pointer to the first node (NULL if none)
    node* last;  // The pointer to the last node (NULL if none)
    unsigned int size_;

如您所见，列表中充满了指向对象的指针，而不仅仅是普通的旧对象，这让我有点困惑。

以下是规范中的描述：

请注意，虽然此列表是跨包含类型 T 模板化的，但它仅插入和删除指向 T 的指针，而不是 T 的实例。这确保 Dlist 实现知道它拥有插入的对象，如果列表，它负责复制它们被复制，如果列表被销毁，它必须销毁它们。

这是我当前的 insertFront(T* o) 实现：

void Dlist::insertFront(T* o) {
  node* insert = new node();
  insert->o = new T(*o); 
  insert->next = first;
  insert->prev = last;
  first = insert;
}

不过，这似乎是错误的。如果 T 没有复制构造函数怎么办？这如何确保列表中对象的唯一所有权？

我可以这样做：

insert->o = o;

这似乎不安全，因为如果您有：

Object* item = new Object();
dlist.insertFront(item);
delete item;

然后该项目也将被销毁列表。它是否正确？我的理解有问题吗？

谢谢阅读。

注意：虽然这看起来像家庭作业，但事实并非如此。我实际上是一个 java 开发人员，只是通过做一个老派项目来提高我的指针技能。

4

1 回答 1

4

当你有一个指针容器时，你有以下两种使用场景之一：

  1. 给容器一个指针，容器负责在删除包含结构时删除指针。

  2. 一个指向容器的指针，但归调用者所有。当不再需要指针时，调用者负责删除指针。

上面的第 1 点非常简单。

在数字 2 的情况下，预计容器的所有者（可能也是调用者）将在删除项目之前从容器中删除项目。

我故意省略了第三个选项，这实际上是您在第一个代码示例中采用的选项。即分配一个新项目并复制它。我忽略它的原因是调用者可以这样做。

省略它的另一个原因是您可能需要一个可以采用非指针类型的容器。T*通过始终使用而不是要求它成为指针T可能不像您想要的那样灵活。有时您应该将其强制为指针，但我想不出对容器执行此操作的任何用途（在我的脑海中）。

如果您允许用户声明Dlist<MyClass*>而不是Dlist<MyClass>那么该列表的所有者隐含地知道它正在使用指针，这将迫使他们从上面假设场景编号 2。

无论如何，这是您的示例和一些评论：

1.T除非有很好的理由，否则不要分配新项目。这个原因可能只是封装。尽管我在上面提到你不应该这样做，但有时你可能想要这样做。如果没有复制构造函数，那么您的类可能是普通的旧数据。如果复制不是微不足道的，则应遵循三法则。

void Dlist::insertFront(T* o) {
  node* insert = new node();
  insert->o = new T(*o);         //<-- Follow rule of three
  insert->next = first;
  insert->prev = last;
  first = insert;
}

2.这是你通常会做的事情

insert->o = o;

3.插入后不得删除您的项目。将所有权传递给您的容器，或者在您和容器都不再需要它时删除该项目。

Object* item = new Object();
dlist.insertFront(item);
delete item;                     //<-- The item in the list is now invalid
于 2012-11-23T01:17:12.537 回答