Geek Answers Handbook

Cyclic data dependency destructor

Now I create my own adjacency list graph class. I have completed most of the steps except the destructor.

This is my vertex class:

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

This is my Edge class:

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

However, I noticed that when calling the destructor, both classes actually call each other a destructor, so this gives me an infinite loop. Is this design problematic? If not, is there a way to fix this destructor problem? Thanks!

+5
source share
4 answers

However, I noticed that when calling the destructor, both classes actually call each other a destructor, so this gives me an infinite loop. Is this design problematic?

Your current design is really problematic. Dynamically allocated should only be deleted by their owners. As a rule, the owner is the one who created the object, and, as a rule, there is exactly one owner. If there is more than one object, then joint ownership. Co-ownership requires a mechanism — for example, link counting — to track the current number of owners.

Judging by the destructors, your vertices seem to “belong” to several edges, and the edges seem to belong to several vertices. If it weren’t, then your graphics would be rather boring. But you did not implement property tracking.

I recommend using a simpler construction where edges have no vertices and no vertices of their own edges. Both must belong to the parent object, which is possibly called Graph .

+4
source

Since the question is marked with C ++ 11, you should use managed pointers first. Among managed pointers, weak_ptr can help you break the circular dependency:

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

Here, your raw pointers have been changed for shared_ptr s: there is no need to cause deletion on destruction, but you must tell the edges to forget the top (see the description of the chapter and tail below).

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

The raw pointers in the edges are modified for weak_ptr : they are non-proprietary objects that point to a shared resource. You cannot dereference weak_ptr directly: you must invoke the lock method, which creates a temporary shared_ptr for the specified resource, if it exists (thus preventing circular dependency). Using:

 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; }
+2
source

I think this is a design problem, because in terms of the graph - when removing an edge - you should not delete your vertices.

I suppose,

 m_head = nullptr; m_tail = nullptr;

enough in your example.

+1
source

The short answer to your question, like the others, already answered: "Yes, calling each destructor is problematic, because this is likely to lead to undefined behavior .

For example, look at this situation:

  • A Vertex object v is deleted,
  • which m_edge 1st Edge in the m_edge member m_edge ,
  • which m_head both m_head and m_tail Vertex ,
  • Assuming one of them is v , the next loop in v destructor will try to access the remote data!

At best, your program will be segfault; in the worst case ... who knows ...

Your design is not so bad. His problem, however, is that you cannot clearly define ownership (which could help to know who should destroy whom).

In fact, assuming that Vertex can be associated with several (and at least one) Edge and that Edge is in relation to exactly two Vertex , then you can assume that Edge belongs to a pair of Vertex . It is not so easy to control the deletion order in this situation ...

However, you do not necessarily need an attitude of ownership of the state, which should destroy anyone. As suggested above, a Edge matches exactly two Vertex ; if one of them is destroyed, then Edge must also be destroyed. On the other hand, if Edge destroyed, there is no reason to destroy any of Vertex in relation to it, because each of them can still be associated with another existing Edge ; the only exception to this is that Vertex has nothing to do with any Edge . The code following these rules is as follows:

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

Living example

+1
source

More articles:


All Articles