Copy of graph

graph_copy.cpp

#include <iostream>
#include <vector>
#include <map>
#include <functional>

using namespace std;

template<typename T>
class Node;

template<typename T>
void NodeDestroy(Node<T>* ptr) { 
  cout << "~ " << ptr << endl;
  delete ptr; 
}

template<typename T>
void NoOp(Node<T>* ptr) {}


template<typename T>
class Node {
public:
  Node(const T& value) :
    value_(value)
    {}

  ~Node() {
    for(size_t ii = 0; ii < childs_.size(); ++ii) {
      Node* child = childs_[ii];
      destroy_policies_.at(ii)(child);
    }
  }

  const T& value() const { return value_; }

  void addChild(const T& child_value) {
    childs_.push_back(new Node(child_value));
    destroy_policies_.emplace_back(&NodeDestroy<T>);
  }
  
  void addChild(Node* child, bool own_memory) {
    childs_.push_back(child);
    destroy_policies_.emplace_back(&NoOp<T>);
  }
  
  const vector<Node*> childs() const { return childs_; }
  
  void print() const {
    cout << this << ": " << value_ << endl;
    for(const auto* cptr : childs_) {
      cptr->print();
    }
  }
  
  Node* copy() const {
    map<const Node*, Node*> copied_nodes;
    return copyImpl(copied_nodes).first;
  }
      
private:
  using DestroyPolicy = function<void(Node<T>*)>;
  
  pair<Node*, DestroyPolicy> copyImpl(map<const Node*, Node*>& copied_nodes) const {
    if(auto iter = copied_nodes.find(this); iter != copied_nodes.end()) {
      return {iter->second, &NoOp<T>};
    }
    
    Node* new_node = new Node(value_);
    copied_nodes[this] = new_node;
    for(const auto* cptr : childs_) {
      const auto [child_node, policy] = cptr->copyImpl(copied_nodes); 
      new_node->childs_.push_back(child_node);
      new_node->destroy_policies_.push_back(policy);
    }
    
    return {new_node, &NodeDestroy<T>};
  }
  
  
  T value_;
  vector<Node*> childs_;
  vector<DestroyPolicy> destroy_policies_;
};

int main() {
  using Graph = Node<int>;
  Graph root(0);
  root.addChild(1);
  root.addChild(2);
  
  root.childs()[0]->addChild(3);
  
  root.childs()[1]->addChild(4);
  root.childs()[1]->addChild(5);
  root.childs()[1]->childs()[0]->addChild(root.childs()[0], false);
  
  
  root.print();
  
  Graph* root2 = root.copy();
  cout << endl;
  root2->print();
  
  root2->childs()[0]->addChild(root2, false);
  
  delete root2;
  return 0;
}