How to implement a deep copy or clone of an object with circular links?

Question

I have a hierarchy like this:

class Sphere;
class Cube;
class SpherePair;

class Entity {};

class Cube : public Entity {
public:
  list<Sphere*> spheres_;
};

class Sphere : public Entity {
public:
  Cube       *cube;
  SpherePair *spherepair;
};

class SpherePair : public Entity {
public:
  Sphere *first;
  Sphere *second;
};

I want to create a clone of the Cube object and all objects associated with it (Sphere, SpherePair, Cube).

The cube has spheres inside, each sphere is half the SpherePair object. SpherePair points to spheres that are in separate cubes or in the same cube.

This is necessary for the correct functionality of Undo.

I would also like to have a map of old and cloned objects:

std::map<Entity*, Entity*> old_new;

Posted: . Before these circular links, I had simple clone functionality:

class Entity {
 public:
  virtual Entity* clone() = 0;
}

It was used in such a scheme:

std::vector<Entity*> selected_objects_;

void move(const vec3f &offset) {
  document->beginUndo();

  for(int i = 0; i < selected_objects_.size(); ++i) {
    Entity *cloned = selected_objects_[i]->clone();

    cloned->move(offset);

    selected_objects_[i]->setDeleted(true);
    document->pushToUndo(selected_objects_[i]);
    document->addEntity(cloned);
  }

  document->endUndo();
}

Answer 1

I will send all the code as an answer:

#include <iostream>
#include <list>
#include <map>

#include <assert.h>

using std::cout;
using std::endl;
using std::list;
using std::make_pair;
using std::map;
using std::pair;

class Cube;
class Sphere;
class SpherePair;

class Entity {
 public:
  virtual ~Entity() {}
  virtual Entity* clone() { return 0; }
  virtual Entity* cloneDeep(map<Entity*, Entity*> *old_new) { return 0; }

 protected:
  bool cloneAndPush(Entity *e, map<Entity*, Entity*> *old_new) {
    if (0 != old_new->count(e)) {
      return false;                             // already cloned
    }

    typedef pair<map<Entity*, Entity*>::iterator, bool> insert_result;
    Entity *cloned = e->clone();
    insert_result inserted = old_new->insert(std::make_pair(e, cloned));
    assert(inserted.second);
    return inserted.second;
  }
};

class Sphere : public Entity {
public:
  Sphere() {
    cout << "constructor Sphere" << endl;
  }
  virtual ~Sphere() {
    cout << "destructor Sphere" << endl;
  }
  virtual Entity* clone();
  virtual Entity* cloneDeep(map<Entity*, Entity*> *old_new);

  Cube       *cube;
  SpherePair *spherepair;
};

class Cube : public Entity {
 public:
  Cube() {
    cout << "constructor Cube" << endl;
  }
  virtual ~Cube() {
    cout << "destructor Cube" << endl;
  }
  virtual Entity* clone() {
    cout << "clone Cube" << endl;
    Cube *c = new Cube(*this);
    c->spheres_.clear();
    return c;
  }

  virtual Entity* cloneDeep(map<Entity*, Entity*> *old_new) {
    if (cloneAndPush(this, old_new)) {
      Cube *c = static_cast<Cube*>((*old_new)[this]);
      for(list<Sphere*>::iterator i = spheres_.begin(); i != spheres_.end(); ++i) {
        c->addSphere(static_cast<Sphere*>((*i)->cloneDeep(old_new)));
      }
    }

    return old_new->operator[](this);
  }

  void addSphere(Sphere *s) {
    spheres_.push_back(s);
  }

  void delSphere(Sphere *s) {
      spheres_.remove(s);
  }

  list<Sphere*> spheres_;
};

class SpherePair : public Entity {
 public:
  SpherePair() {
    cout << "constructor SpherePair" << endl;
  }
  virtual ~SpherePair() {
    cout << "destructor SpherePair" << endl;
    delete first;
    delete second;
  }

  virtual Entity* clone() {
    cout << "clone SpherePair" << endl;
    return new SpherePair(*this);
  }

  virtual Entity* cloneDeep(map<Entity*, Entity*> *old_new) {
    if (cloneAndPush(this, old_new)) {
      SpherePair *s = static_cast<SpherePair*>((*old_new)[this]);
      s->first = (Sphere*)first->cloneDeep(old_new);
      s->second = (Sphere*)second->cloneDeep(old_new);
    }

    return (*old_new)[this];
  }

  Sphere *first;
  Sphere *second;
};

Entity* Sphere::clone() {
  cout << "clone Sphere" << endl;
  return new Sphere(*this);
}

Entity* Sphere::cloneDeep(map<Entity*, Entity*> *old_new) {
  if (cloneAndPush(this, old_new)) {
    Sphere *s = static_cast<Sphere*>((*old_new)[this]);
    s->cube = (Cube*)cube->cloneDeep(old_new);
    s->spherepair = (SpherePair*)spherepair->cloneDeep(old_new);
  }

  return (*old_new)[this];
}

inline void populateListSimpleCase(list<Entity*> *ents) {
  Cube *first_cube = new Cube;
  Cube *second_cube = new Cube;
  // Cube *third_cube = new Cube;
  ents->push_back(first_cube);
  ents->push_back(second_cube);

  for (int i = 0; i < 3; ++i) {
    Sphere *first_cube_spheres = new Sphere;
    Sphere *second_cube_spheres = new Sphere;
    first_cube->addSphere(first_cube_spheres);
    first_cube_spheres->cube = first_cube;

    second_cube->addSphere(second_cube_spheres);
    second_cube_spheres->cube = second_cube;

    SpherePair *sp = new SpherePair;
    sp->first = first_cube_spheres;
    sp->second = second_cube_spheres;
    ents->push_back(sp);
    first_cube_spheres->spherepair = sp;
    second_cube_spheres->spherepair = sp;
  }
}

int main(int argc, char* argv[]) {
  list<Entity*> ent_list;
  populateListSimpleCase(&ent_list);

   map<Entity*, Entity*> old_new;
   (*ent_list.begin())->cloneDeep(&old_new);

  for (list<Entity*>::iterator i = ent_list.begin(); i != ent_list.end(); ++i){
    delete (*i);
  }
  ent_list.clear();

  return 0;
}

Answer 2

: . - . , , , , . , , ( ).

...

.

, , . ( ) , , , .

, , - - "" . DAG, .

Answer 3

. , , , . ++ FAQ , : http://www.parashift.com/c++-faq-lite/serialization.html\

I always come back here when I need to do something like this.

Answer 4

Not sure if this is what you want, but here comes the cloning of the graph (with or without circular links)

#include <iostream>
#include <map>
using namespace std;

struct Thing{
 int length;
 int id;
 Thing *things[];
};

Thing* deepCopy(Thing *aThing,map<Thing*, Thing*> &aMap){

 Thing *newThing = new Thing();
 newThing->length = aThing->length;
 newThing->id = aThing->id;
 for(int i = 0 ;i < aThing->length;i++){
      auto it1 = aMap.find(aThing->things[i]);
      if(it1 == aMap.end()){
         aMap.insert(pair<Thing*,Thing*>(aThing,newThing));
         newThing->things[i] = deepCopy(aThing->things[i],aMap);
      }else{
         newThing->things[i] = it1->second;
      }
 }
 return newThing;    
}

int main(){

 Thing *aThing1 = new Thing();
 Thing *aThing2 = new Thing();
 Thing *aThing3 = new Thing();


 //////INITIALIZE GRAPH ///////// You can ignore this block
 aThing1->length = 2;
 aThing1->id = 1;
 aThing2->length = 2;
 aThing2->id = 2;
 aThing3->length = 1;
 aThing3->id = 3;
 aThing1->things[0] = aThing2; 
 aThing1->things[1] = aThing3; 
 aThing2->things[0] = aThing1; 
 aThing2->things[1] = aThing3; 
 aThing3->things[0] = aThing2; 
 //////END INITIALIZE GRAPH ///////// You can ignore this block
 map<Thing*,Thing*> aMap;
 Thing *myNewThing = deepCopy(aThing1,aMap);
 return 0;
}

I got this in an interview, and I struggled to get it right. I came very close to the solution, but instead of a map I used a set, so the search was a bit complicated.

The only important part is the deepCopy method. The rest is just boilerplate code.