Дискруктор зависимостей циркулярных данных

Question

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

Это мой Vertex класс:

struct Vertex{ 
public: 
    Vertex(){m_name="";} 
    Vertex(string name):m_name(name){} 
    ~Vertex(){ 
     cout << "vertex des" << endl; 
     for(int i = 0; i < m_edge.size(); i++){ 
      delete m_edge[i]; 
      m_edge[i] = nullptr; 
     } 
    } 
    string m_name; 
    vector<Edge*> m_edge; 
}; 

Это мой край Класс:

struct Edge{ 
public: 
    Edge() : m_head(nullptr), m_tail(nullptr) {m_name="";} 
    Edge(string name) : m_name(name), m_head(nullptr), m_tail(nullptr) {} 

    ~Edge(){ 
     cout << "Edge des" << endl; 

     delete m_head; 
     m_head = nullptr; 
     delete m_tail; 
     m_tail = nullptr; 
    } 

    string m_name; 

    Vertex* m_head; 
    Vertex* m_tail; 
}; 

Однако, я заметил, когда вызывается деструктор, оба 2 класса на самом деле назвать деструктор друг друга, так что это дает я бесконечный цикл. Является ли этот дизайн проблематичным? Если нет, есть ли способ исправить эту проблему деструктора? Благодаря!

Answer 1

Однако, я заметил, что при вызове деструктора оба класса на самом деле называют деструктор друг друга, поэтому это дает мне бесконечный цикл. Является ли этот дизайн проблематичным?

Ваш текущий дизайн действительно проблематичен. Динамически выделяемые должны быть удалены только их владельцами . Как правило, владельцем является тот, кто создал объект, и, как правило, существует ровно один владелец. Если существует более одного объекта, тогда собственность поделилась. Для совместного владения требуется механизм - например, подсчет ссылок - для отслеживания текущего количества владельцев.

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

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

Answer 2

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

Я полагаю,

m_head = nullptr; 
m_tail = nullptr; 

достаточно в вашем примере.

Answer 3

Поскольку вопрос отмечен C++ 11, вы должны сначала использовать управляемые указатели. Среди управляемых указателей, weak_ptr может помочь вам преодолеть круговую зависимость:

#include <vector> 
#include <memory> 
#include <string> 
#include <iostream> 

using namespace std; 

struct Edge; 

struct Vertex{ 
public: 
    Vertex(){m_name="";} 
    Vertex(string name):m_name(name){} 
    ~Vertex(){ 
     cout << "vertex des" << endl; 
     for(auto e : m_edge) 
     { 
      if(e->m_head.lock().get() == this) 
      { 
       e->m_head = nullptr; 
      } 
      if(e->m_tail.lock().get() == this) 
      { 
       e->m_tail = nullptr; 
      } 
     } 
    string m_name; 
    vector<shared_ptr<Edge>> m_edge; 
}; 

Здесь ваши сырые указатели были изменены для shared_ptr с: нет необходимости вызывать удаление на уничтожение, но вы должны сказать края забыть вершину (см заголовка и хвоста ниже).

struct Edge{ 
public: 
    Edge(){m_name="";} 
    Edge(string name):m_name(name){} 

    ~Edge(){ 
     cout << "Edge des" << endl; 
     // if you're here, this means no vertices points to the edge any more: 
     // no need to inform head or tail the edge is destroyed 
    } 

    void do_something_to_head() 
    { 
     auto head = m_head.lock(); 
     if(head) 
     { 
      head->do_something(); 
     } 
    } 

    string m_name; 

    weak_ptr<Vertex> m_head; 
    weak_ptr<Vertex> m_tail; 
}; 

Необработанные указатели в ребрах изменяются для weak_ptr: они «не владеющих» объекты, указывающие на общий ресурс. Вы не можете разыменовать weak_ptr напрямую: вы должны вызвать метод lock, который создает временный shared_ptr указанному ресурсу, если он существует (таким образом предотвращая циклическую зависимость).Использование:

int main() 
{ 
    shared_ptr<Vertex> v1 = make_shared<Vertex>(); 
    shared_ptr<Vertex> v2 = make_shared<Vertex>(); 

    // connection should be encapsulated somewhere 

    shared_ptr<Edge> e = make_shared<Edge>(); 

    v1->m_edge.push_back(e); 
    e->m_head = v1; 

    v2->m_edge.push_back(e); 
    e->m_tail = v2; 

    return 0; 
} 

Answer 4

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

Например, посмотрите на эту ситуацию:

• Vertex объект v время удаления
• , что приводит к удалению 1 Edge в векторе член m_edge,
• , что приводит к удалению оба m_head и m_tailVertex,
• Предполагая, что один из них v, затем следующий цикл в v деструктор попытается получить доступ к удаленным данным!

В лучшем случае ваша программа будет segfault; в худшем случае ... кто знает ...

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

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

Однако вам не обязательно нужно отношение собственности к государству, которое должно уничтожить кого. Как предполагалось выше, Edge относится к точно двум Vertex; если один из них уничтожен, то также должен быть уничтожен Edge. С другой стороны, если уничтожен Edge, нет никаких оснований для уничтожения любого из Vertex по отношению к нему, поскольку каждый из них по-прежнему может быть связан с другими существующими Edge; единственным исключением является то, что Vertex не имеет никакого отношения к любому Edge. Код следующие правила является следующее:

struct Edge; 

struct Vertex { 
public: 
    // ctors unchanged 
    ~Vertex(); // implemented below 
    void remove_relation(Edge* edge) // for use by Edge only 
    { 
     std::vector<Edge*>::iterator it = 
      std::find(m_edge.begin(), m_edge.end(), edge); 
     if (it != m_edge.end()) 
      m_edge.erase(it); 
     if (m_edge.size() == 0) 
      delete this; // this Vertex can be safely deleted 
    } 
    string  m_name; 
    vector<Edge*> m_edge; 
}; 

struct Edge { 
public: 
    // ctors unchanged 
    ~Edge() { 
     // Only have to remove relation with m_head & m_tail 
     if (m_head) 
      m_head->remove_relation(this); 
     if (m_tail) 
      m_tail->remove_relation(this); 
     std::cout << "deleted Edge " << this << std::endl; 
    } 
    void delete_from_vertex(Vertex* from) // for use by Vertex only 
    { 
     // Prevent from removing relation with the calling Vertex 
     if (m_head == from) 
      m_head = nullptr; 
     else if (m_tail == from) 
      m_tail = nullptr; 
     else 
      assert(false); // Vertex not in relation with this Edge 
     delete this;  // finally destroy this Edge 
    } 
    string m_name; 
    Vertex* m_head; 
    Vertex* m_tail; 
}; 

Vertex::~Vertex() { 
    for(int i = 0; i < m_edge.size(); i++) 
     m_edge[i]->delete_from_vertex(this); // special destruction 
    std::cout << "deleted Vertex " << this << std::endl; 
} 

Live example