Deep copy of tree data structure in C++ without boilerplate copy code?

Question

Suppose I have a tree data structure implemented with node class:

class Node
{
  Node * parent;
  std::vector<Node*> children;
  int data_1;
  std::string data_2;
  double data_3;
  ...
  float data_n;
};

To do a deep copy, is there any way to get around writing all of the boilerplate copying for the non-pointer properties? All of the

that.data_1 = this->data_1;
that.data_2 = this->data_2;
...
that.data_n = this->data_n;

I know in advance that the number of pointer properties is small and will not change. However, the non-pointer properties is larger and fluctuates as I develop my program. Thus, I'd rather avoid needing to remember to add this boilerplate code every time I add a new property.

(I'm willing to use C++11 and less enthusiastically boost)

You could wrap all the nonpointers in a struct and then just copy the struct. Would add an extra dot to all the accesses, though. Alternately, wrap the *pointers* in a substruct, and give it its own copy constructor. — dlf, May 05 '14 at 21:33
similarly`std::tuple` could probably be used but that would also make data accessing more complex. — YoungJohn, May 05 '14 at 21:37
Wrapping the pointers in a struct or class might also help you separate your concerns. After all, if the pointers are all related (ie used for node traversal) bundling them together may allow you to hand them off to functions or algorithms that don't care about the rest of the data. — YoungJohn, May 05 '14 at 21:54

score 1 · Answer 1 · answered May 05 '14 at 21:43

1

As hinted in comments you can wrap data in a struct, then just copy a structure and handle the rest of the copying process in copy constructor body:

class Node
{
  Node * parent;
  std::vector<Node*> children;
  //... maybe more

  struct Data {
      int data_1;
      std::string data_2;
      double data_3;
      ...
      float data_n;
  }
  Data data;
  Node( Node const& other) : data( other.data) {
      //... do the rest
  }
};

answered May 05 '14 at 21:43

4pie0

29,204
9
82
118

Nice. So this solution incurs the extra dot for accessing: `my_node->data_1` becomes `my_node->data.data_1`? – Alec Jacobson May 05 '14 at 21:57
Is there a way to template _and_ derive a class like this? Templating on `Data` seems easy, but I can't imagine how to derive from Node since the derived class should have derived class `children`, so I can't do the nasty part of the deep copy inside Node. (Why is implementing a tree with parent pointers so elusive? Or does everyone maintain boilerplate copy and `op=` routines?) – Alec Jacobson Oct 23 '14 at 23:22

jthill · Answer 2 · 2014-05-05T22:19:46.097

0

You can put the payload in a base class:

struct i {
        i(int a, float b) : a(a), b(b) {}
        int a;
        float b;
};

struct n : i {
        using i::i;
        n(const n&r) : i(r) {}
};

n N {1,1.0};

int main()
{
        n M {0,1.0};
        M=N;
        return M.a;
}

which has other advantages too, I've gotten fond of separating content from structure.

edited May 05 '14 at 22:19

answered May 05 '14 at 22:14

jthill

55,082
5
77
137

inheritance should be used for expressing *is a kind of* relationship. At least private inheritance should be used in this case – 4pie0 May 05 '14 at 22:27
@privatedatapublicchannel2 That's an odd constraint. Can't say I see any value in categorically outlawing the [CRTP](http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern) and all similar techniques. Seems to me you're deep in "[not simpler](http://quoteinvestigator.com/2011/05/13/einstein-simple)" territory here. (edit: replaced garbled link post-5min limit, so rewrote). – jthill May 06 '14 at 00:28

score 0 · Answer 3 · answered May 06 '14 at 10:43

0

If you only need a recursive container you could use Boost.Container. It is designed with these use cases in mind. The problem I see with you code is the pointer to parent. I think this can not be simply implemented. But you will get memory management for free.

answered May 06 '14 at 10:43

Jan Herrmann

2,717
17
21

If I don't want the parent pointer, do I really need boost containers? Won't stl containers suffice? – Alec Jacobson Oct 23 '14 at 21:36
@mangledorf no. See http://stackoverflow.com/questions/18672135/why-c-containers-dont-allow-incomplete-types and http://www.boost.org/doc/libs/1_55_0/doc/html/container/main_features.html#container.main_features.containers_of_incomplete_types . As long as you need recursive containers you have an incomplete type. – Jan Herrmann Oct 24 '14 at 13:05

Deep copy of tree data structure in C++ without boilerplate copy code?

3 Answers3