Как реализовать глубокое копирование или клонирование объекта, который имеет циклические ссылки?

Question

У меня есть такая иерархия:

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

Я хочу сделать клон объекта Cube и всех объектов, связанных с ним (Sphere, SpherePair, Cube).

Куб имеет сферы внутри, каждая сфера - это половина объекта SpherePair.SpherePair указывает на сферы, которые находятся в отдельных кубах или в одном и том же кубе.

Это необходимо для правильной функциональности отмены.

Я также хотел бы иметь карту старых и клонированных сущностей:

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

Добавлено: До этих циклических ссылок у меня была простая функция клонирования:

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

Использовалась такая схема:

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

Я опубликую весь кодовый блок в качестве ответа:

#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

Не уверен, что это то, что вам нужно, но здесь идет клонирование графика (с или без циклических ссылок)

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

Я получил это в интервью, и я изо всех сил пытался сделать это правильно.Я очень близко подошел к решению, но я использовал набор вместо карты, поэтому поиск был немного сложным.

Единственная важная часть - это метод deepCopy.Остальное просто шаблонный код.

Answer 3

Вы можете рассматривать это как особый случай сериализации и десериализации. Вы сериализуете объект, который хотите скопировать в поток байтов, а затем десериализуете его в новый объект. Этот C ++ FAQ содержит несколько полезных советов о том, как сериализовать все более и более сложные графы объектов: http://www.parashift.com/c++-faq-lite/serialization.html\

Я всегда возвращаюсь сюда, когда мне нужно сделать что-то подобное.

Answer 4

Что касается вашего общего вопроса: рассматривайте структуру как граф с объектами в памяти как вершинами и указателями как ребра. Пройдите структуру в глубину в первую очередь. Сохраните карту, изначально пустую, адресов узлов в старой структуре к адресам узлов в новой структуре, путем поверхностного копирования структуры и установки указателей один за другим. Останавливайте рекурсию каждый раз, когда вы сталкиваетесь с подструктурой, адрес которой уже виден (находится на карте).

Однако ...

Это необходимо для правильной работы функции отмены.

Я не уверен, что понял вашу точку зрения, но вам не нужны циклические ссылки для отмены. Вместо этого используйте циклический буфер (который на самом деле представляет собой простой массив с несколькими флагами и указателями) и, если возможно, используйте совместное использование структуры, чтобы снизить требования к памяти.

Если вы имели в виду, что для отмены вам нужна глубокая копия, тогда я все же рекомендую вам рассмотреть какое-то «плоское» представление графа для ваших объектов. Структуры указателей отлично подходят для деревьев и групп DAG, но очень запутаны при использовании для общих графов.