Newbie question about manual memory management and deep copying

Question

Alright, so I'm trying out C++ for the first time, as it looks like I'll have to use it for an upcoming course in college. I have a couple years of programming under my belt, but not much in the non-garbage-collected world.

I have a class, a Node for use in a doubly linked list. So basically it has a value and two pointers to other Nodes. The main constructor looks like Node(const std::string & val, Node * prev, Node * next). The exercise includes a copy constructor that does a shallow copy of another Node, with a comment above it that says to change it to make a deep copy.

Here is what I thought that meant:

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

This seems to accomplish the goal of making it so that changing the copied Node doesn't affect the new Node. However, when I do it this way, I am allocating new stuff on the heap. This worries me, because I think it means that I should also be deleting it in the Node's destructor. But this is now inconsistent with the other constructor, where pointers to the Nodes are just passed in, already pointing to something. I can't rightly go deleteing next and prev in the destructor with that going on, right?

I'm really confused, guidance appreciated!

EDIT: Here is the code (before my above change to it), as requested:

#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

Usually "deep copy" involves traversing the data structure and copying the entire thing. In your case, given a Node, make a complete copy of the list.

Answer 2

A deep copy makes an entire copy of a structure. What I mean by structure is a collection of objects that work together to perform a task. If you had a car class that had an object for each wheel and the body - a deep copy would make a copy of the entire car (and make copies of both the wheels and the body).

In your case, the "Entire Structure" is the list. A deep copy operation would only make sense if performed at the "list level." A deep copy of a node would copy the data that the node points to - but would not assign itself to be part of a list (as a Node should be unaware of the "master" list object).

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

Note: I just pulled that code out of my ass so it's not tested. Hope it helps though :)

Answer 3

First of all, I'm not really sure how the objective of the exercise should be understood. How deep should the copy be? In a solution like yours, this->next->next and other.next->next would be still the same thing. Should this object also be duplicated? And the rest of the list? Where does it end? One could of course deep-copy the whole list, but this would be a quite unexpected behavior of a copy constructor of a single node, I think.

Is maybe the value member variable a pointer, that is supposed to be deep copied? That would make much more sense for me.

But back to your interpretation:

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

There are two problems with your implementation. For one b->next->prev points to a, while I suspect it should point back to b. Secondly you need to think about the corner cases, where a might be the first or last node in the list.

And to your main question: you are of course right, somewhere the newly created objects need to be deleted again. No matter if you just copy the prev and next nodes or the whole list, I would say the user of that copy is responsible to delete all the copied nodes again. I assume with a normal, not-copied list, the user of that list would walk through all the nodes and delete them manually one after another, once he's done with the list. He wouldn't not assume the destructor of one node to delete the whole list. And the same goes for copies, they should behave the same. The user of the copied stuff should delete all the copies. (In practice you would probably have a list class, that does all that node management for you).

But again, if the copy constructor of the node copies the whole list, or even just several of it's nodes, this would be very unexpected and all the time people would forget to clean up all these copies. But that's not your node class' fault, but the exercise requirements'.

Answer 4

You are correct in worrying.

By passing pointers into the Node constructor there is no information about ownership passed with the pointer. This is a poor design of the constructor. Either you should pass in a reference indicating you don't own the next node or pass a std::auto_ptr<> which indicates that you must take ownership. One could argue that the next or prev could be NULL (beginning or end of the list) and thus you can not use references, but this can be overcome by having alternative constructors.

Of course there are exceptions:
Is the Node class a private member of another class. If this is the case the use of the Node class is completely controlled by the owner and thus its correct usage would be controlled by the owning class.

What you have not provided is the definition of the destructor. With this we will be able to tell if the node is actually taking ownership of the pointer that are passed in to the constructors (or if the next and prev are already smart pointers)?

Answer 5

If every node makes copies of the nodes it points to then you can safely delete the objects in the destructors. If you are passing pointers (as the constructor Node(const std::string & v, Node * p, Node * n)) does then you do not "own" the pointers and should not delete them. If this is part of a linked list class then that class should own the pointers and delete the objects as necessary. You could also make Node a private subclass of the linked list class to avoid users (or yourself) messing with your pointers.

You've made a mistake in the recursion in your implementation as well, the copy constructor contains one level of a deep copy and calls the "normal" constructor, which takes pointers, making it shallow. What this means is that your deep copying is only one level deep. It should repeatedly call the copy constructor, something like this:

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

AFAIK there is no benefit to using a deep copy here though, the only practical application I can think of is when copying the entire list, which could be handled more effectively in the class representing said list.