Deep copy of struct C++

Question

Say I have a struct:

struct TrieNode {
const NumChars = 26;
bool isWord;
int letterCount;
TrieNode *letters[NumChars];

TrieNode() {
    isWord = false;
    for ( int i = 0; i < NumChars; i += 1 ) {
        letters[i] = NULL;
    } // for
    letterCount = 0;
 }
};

I create a TrieNode on the heap like this:

TrieNode *root = new TrieNode();

Now how can I create a different copy of root? (deep copy)

`TrieNode():isWord(),letters(),letterCount(){}` is simpler than what you have. — Mooing Duck, Oct 30 '12 at 21:52
@MooingDuck Man, I stop counting how many questions we answered by "read a book" today. — Etienne de Martel, Oct 30 '12 at 21:53
Is this homework? I'm going to delete my answer until I hear if it is or not. I'm really irritated that the homework tag has become discouraged. — Omnifarious, Oct 30 '12 at 22:09
Not really homework, just using it as an example from my notes to study for an exam. — thisiscrazy4, Oct 30 '12 at 22:20
@thisiscrazy4: I've undeleted it then because my answer basically gave you the answer in full. — Omnifarious, Oct 30 '12 at 22:26

score 4 · Answer 1 · edited May 23 '17 at 12:12

In C++ you can do this be defining a custom "copy constructor". It would be of the form:

TrieNode(const TrieNode& copyFrom){
  //Do the copying here
}

Then you can use this pretty much anyway you want:

TrieNode example;
TrieNode deep(example);
TrieNode deep2 = example;

If you want to define a copy constructor, chances are you'll also want to define a destructor and an assignment operator. This is called the Rule of 3.

If you implement the assignment operator (=) then you can also write code like:

TrieNode example;
TrieNode deep;
//Do stuff
deep = example; //Still a deep copy.

score 2 · Answer 2 · answered Oct 30 '12 at 21:53

You write a recursive routine to do the copy. I.e. a routine that copies isWord and letterCount and then calls itself recursively on each non-NULL element of letters. You can make this routine a copy constructor or not. Whatever makes most sense for the rest of your code.

Omnifarious · Answer 3 · 2012-10-30T22:19:24.627

struct TrieNode {
   static const NumChars = 26;
   bool isWord;
   int letterCount;
   TrieNode *letters[NumChars];

   TrieNode() : isWord(false), letterCount(0) {
      for ( int i = 0; i < NumChars; i += 1 ) {
         letters[i] = NULL;
      } // for
   }
   TrieNode(const TrieNode &other)
       : isWord(other.isWord), letterCount(other.letterCount)
   {
      for ( int i = 0; i < NumChars; ++i ) {
         if (other.letters[i]) {
            letters[i] = new TrieNode(other.letters[i]);
         } else {
            letters[i] = NULL;
         }
      }
   }
};


TrieNode *root = new TrieNode();
TrieNode *deepcopy = new TrieNode(*root);

It's a recursive data structure, so you need a recursive copying algorithm. Notice how the copy constructor I made calls itself to create the sub-nodes?

IMHO, the thing has several design flaws. But you didn't ask to fix them, you just asked how to make a deep copy of it.

Deep copy of struct C++

3 Answers3