代码之家 › 专栏 › 技术社区 › J Cooper

关于手动内存管理和深度复制的新手问题

deep-copy memory-management c++

J Cooper · 技术社区 · 17 年前

我有一个类,一个用于双链接列表的节点。所以基本上它有一个值和两个指向其他节点的指针。主构造函数看起来像 Node(const std::string & val, Node * prev, Node * next) . 该练习包括一个复制构造函数,它对另一个节点进行浅层复制,上面有一条注释,表示要将其更改为深度复制。

以下是我认为的意思:

Node(const Node & other)
      : value(other.value)
{
  prev = new Node(other.prev->value, other.prev->prev, other.prev->next);
  next = new Node(other.next->value, other.next->prev, other.next->next);
}

delete 惯性导航与制导 next 和 prev

我真的很困惑,谢谢!

编辑:以下是代码(在我对其进行上述更改之前),按要求:

#include <string>

//! Node implements a doubly-linked list node
class Node {
    friend class LinkedList;  //!< LinkedList can access private members of Node
public:

    //!  Constructor
    Node(const std::string & v, Node * p, Node * n) :
      value(v), prev(p), next(n)
    {
    }

    //! Change to deep copy
    Node(const Node & other) :
      value(other.value), prev(other.prev), next(other.next)
    {
    }

    //!  Read-only public methods for use by clients of the LinkedList class
    const std::string & GetValue() const
    {
      return value;
    }


    Node * GetPrevious()const
    {
      return prev;
    }


    Node * GetNext()const
    {
      return next;
    }

    //! Change to deep copy
    Node & operator=(const Node & other)
    {
        if(this!=&other)
        {
            value=other.value;
            prev=other.prev;
            next=other.next;
        }
        return *this;
    }

 private:
    std::string value;        //!< value stored in the node
    Node * prev;            //!< pointer to previous node in the list
    Node * next;            //!< pointer to next node in the list
};

5 回复 | 直到 17 年前

sth 17 年前

首先,我不确定该如何理解这个练习的目标。副本应该有多深?在像你这样的解决方案中, this->next->next 和 other.next->next 还是一样。这个对象也应该复制吗?名单的其余部分呢?它在哪里结束?当然,可以深度复制整个列表,但我认为,对于单个节点的复制构造函数来说,这将是一种非常意外的行为。

也许是 value 成员变量一个指针,应该被深度复制吗?这对我来说更有意义。

但回到你的解释:

Node a(...);
// ... more code that adds a whole list to a
Node b(a);

b->next->prev 指向 a ,而我怀疑它应该指向 b . 第二,你需要考虑一些角落的案例,在哪里 A. 可能是列表中的第一个或最后一个节点。

delete 我又哭了。不管你是否只是复制 prev 和 next 节点或整个列表,我认为该副本的用户负责再次删除所有复制的节点。我假设,对于一个普通的、未复制的列表,该列表的用户将遍历所有节点,并在处理完该列表后手动逐个删除它们。他不会假设一个节点的析构函数会删除整个列表。复制品也是如此,它们的行为应该是一样的。复制内容的用户应删除所有副本。(实际上,你可能会有一个 list 类,它为您完成所有节点管理)。

但是,同样,如果节点的复制构造函数复制整个列表,甚至只是复制它的几个节点,这将是非常意外的,而且人们总是会忘记清理所有这些副本。但这不是节点类的错误,而是练习要求。

Mark James 17 年前

通常,“深度复制”涉及遍历数据结构并复制整个内容。在您的情况下,给定一个节点,制作列表的完整副本。

user19302 user19302 17 年前

深度副本生成结构的完整副本。我所说的结构是指一起工作以执行任务的对象的集合。如果您有一个car类,该类的每个车轮和车身都有一个对象,那么深度副本将生成整个汽车的副本(并同时生成车轮和车身的副本)。

在您的例子中,“整个结构”就是列表。深度复制操作只有在“列表级别”执行时才有意义。节点的深度复制会复制节点指向的数据,但不会将自身指定为列表的一部分(因为节点应该不知道“主”列表对象)。

List* List::CopyList()
{
    List* nlist = new List();
    ListNode* node = NULL, prev = NULL;
    ListNode* newNodes = new ListNode[m_nodeCount];
    int i = 0;
    while ((node == NULL && node = m_first) || (node = node->Next()) != NULL)
    {
        newNodes[i] = node->CopyNode(); // also makes a new copy of the node's data
        newNodes[i]->SetNext(NULL);
        newNodes[i]->SetPrev(prev);
        if (prev) prev->SetNext(newNodes[i]);
        prev = newNodes[i];
        ++i;
    }

    if (m_len > 0)
        nlist->SetFirst(newNodes[i]);
    if (m_len > 1)
        nlist->SetLast(newNodes[m_len - 1]);
    return nlist;
}

注意:我只是把代码从我屁股里拔出来,所以它没有经过测试。但希望能有所帮助:)

Loki Astari 17 年前

通过将指针传递到节点构造函数中,没有与指针一起传递的所有权相关的信息。这是一个糟糕的构造函数设计。您应该传入一个表示您不拥有下一个节点的引用,或者传入一个std::auto_ptr<&燃气轮机;这表明你必须拥有所有权。有人可能会认为next或prev可以为NULL(列表的开头或结尾),因此不能使用引用,但这可以通过使用替代构造函数来克服。

当然也有例外:
节点类是另一个类的私有成员。在这种情况下,节点类的使用完全由所有者控制,因此其正确使用将由所有者类控制。

您没有提供的是析构函数的定义。有了它,我们就可以知道节点是否真正拥有传递给构造函数的指针(或者next和prev是否已经是智能指针)?

jheriko 17 年前

如果每个节点都复制了它所指向的节点,则可以安全地删除析构函数中的对象。如果您正在传递指针(就像构造函数节点(const std::string&v,Node*p,Node*n))那样),那么您不“拥有”指针,也不应该删除它们。如果这是链表类的一部分,那么该类应该拥有指针,并根据需要删除对象。您还可以将节点设置为链表类的私有子类,以避免用户(或您自己)弄乱指针。

您在实现中的递归中也犯了一个错误,复制构造函数包含一个深度副本的级别,并调用“普通”构造函数,该构造函数接受指针,使其变浅。这意味着深度复制只有一级深度。它应该重复调用复制构造函数,如下所示:

Node(const Node & other) : value(other.value)
{
  prev = new Node(*(other.prev));
  next = new Node(*(other.next));
}

好吧,在这里使用深度复制没有任何好处,但我能想到的唯一实际应用是复制整个列表,这可以在表示所述列表的类中更有效地处理。