關於手動內存管理和深度複製的新手問題

Question

好的，所以我第一次嘗試C++，因爲它看起來像我將不得不使用它在即將到來的大學課程。我有幾年的編程經驗，但在非垃圾收集的世界中並沒有太多。

我有一個類，一個雙向鏈表中使用的節點。所以基本上它有一個值和兩個指向其他節點的指針。主構造器看起來像Node(const std::string & val, Node * prev, Node * next)。練習包括一個複製構造函數，它執行另一個Node的淺表副本，並在其上面添加一條評論，表示要將其更改爲深度副本。

這是我認爲的意思：

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); 
} 

這似乎實現使它以便更改複製的節點不會影響新節點的目標。但是，當我這樣做時，我正在堆上分配新東西。這讓我很擔心，因爲我認爲這意味着我也應該在Node的析構函數中刪除它。但是現在這與其他構造函數不一致，其中指向節點的指針剛剛被傳入，已經指向某個東西。我不能正確使用delete ing 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 
}; 

Answer 1

首先，我不太清楚如何理解練習的目的。該副本應該有多深？在像你這樣的解決方案中，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 d。無論您是僅複製prev和next節點還是整個列表，我都會說該副本的用戶有責任再次刪除所有複製的節點。我假設有一個正常的，未複製的列表，該列表的用戶將遍歷所有節點，並在他完成列表後一個接一個地手動刪除它們。他不會假設一個節點的析構函數刪除整個列表。對於副本也是一樣，他們應該表現得一樣。複製的東西的用戶應該刪除所有的副本。 （實際上，你可能有一個list類，它可以爲你完成所有的節點管理）。

但是，如果節點的複製構造函數複製了整個列表，甚至只是其中的幾個節點，這將是非常意外的，並且人們總會忘記清除所有這些副本。但這不是你的節點類錯誤，而是練習要求。

Answer 2

通常「深拷貝」涉及遍歷數據結構和複製整個事情。在你的情況下，給定一個節點，做一個完整的副本。

Answer 3

深層副本會生成整個結構的副本。我所說的結構是指一起工作來執行任務的對象集合。如果你有一個汽車班，每個車輪和身體都有一個物體 - 深度複製將製作整個車的副本（並製作車輪和車身的副本）。

就你而言，「整個結構」就是這個列表。只有在「列表級」執行深層複製操作纔有意義。節點的深層副本將複製節點指向的數據 - 但不會將其自身分配爲列表的一部分（因爲節點應該不知道「主」列表對象）。

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; 
} 

注：我只是從我的屁股拉出代碼，所以它沒有測試。希望它有幫助，雖然:)

Answer 4

你是正確的擔心。

通過將指針傳遞到Node構造函數中，沒有關於通過指針傳遞的所有權的信息。這是構造函數的糟糕設計。要麼你應該傳入一個表明你沒有擁有下一個節點的引用，或者傳遞一個表示你必須擁有所有權的std :: auto_ptr>。有人可能會爭辯說next或prev可能是NULL（列表的開頭或結尾），因此您不能使用引用，但可以通過使用其他構造函數來克服。

當然也有例外：
Node類是另一個類的私有成員。如果是這種情況，Node類的使用完全由擁有者控制，因此它的正確用法將由擁有類來控制。

你沒有提供的是析構函數的定義。有了這個，我們將能夠判斷節點是否實際接受了傳遞給構造函數的指針的所有權（或者如果next和prev已經是智能指針）？

Answer 5

如果每個節點都創建它指向的節點的副本，則可以安全地刪除析構函數中的對象。如果你傳遞指針（作爲構造函數Node（const std :: string & v，Node * p，Node * n）），那麼你不會「擁有」這些指針，也不應該刪除它們。如果這是鏈接列表類的一部分，那麼該類應擁有指針並根據需要刪除對象。你也可以使Node成爲鏈表類的私有子類，以避免用戶（或你自己）搞砸你的指針。

您在實現中的遞歸中也犯了一個錯誤，複製構造函數包含深層副本的一個級別，並調用「正常」構造函數，該構造函數接受指針，使其變淺。這意味着您的深層複製只有一層深度。應該反覆調用拷貝構造函數，像這樣：

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

AFAIK有在這裏使用一個深拷貝，雖然沒有任何好處，唯一的實際應用中複製整個列表時，我能想到的是，這可能是在代表所述列表的班級中更有效地處理。