我现在正在设计自己的带有邻接列表的图类。我完成了除析构函数之外的大部分步骤。
这是我的顶点类:
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;
};
但是,我注意到当调用析构函数时,两个类实际上都调用了彼此的析构函数,因此这给了我一个无限循环。这个设计有问题吗?如果没有,有没有办法解决这个析构函数问题?谢谢!
但是,我注意到当调用析构函数时,两个类实际上都调用了彼此的析构函数,因此这给了我一个无限循环。这个设计有问题吗?
你现在的设计确实有问题。动态分配只能由其各自的所有者删除。通常,所有者是创建对象的人,通常只有一个所有者。如果有多个对象,则共享所有权。共享所有权需要一种机制(例如引用计数(来跟踪当前所有者的数量。
从构造器来看,您的顶点似乎由多条边"拥有",而边似乎由多个顶点拥有。如果不是这种情况,那么你的图表会很无聊。但是您尚未实施任何形式的所有权跟踪。
我建议使用更简单的设计,其中边不拥有顶点,顶点也不拥有边。它们都应该由可能称为 Graph
的父对象拥有。
由于问题标记为 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
s:无需在销毁时调用 delete,但您应该告诉边缘忘记顶点(请参阅下面的头尾声明(。
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;
}
这是一个设计问题,因为,在图形术语中 - 当您删除边缘时 - 您不应该删除其顶点。
我想,
m_head = nullptr;
m_tail = nullptr;
在你的例子中就足够了。
像其他人已经回答的那样,对您的问题的简短回答是:是的,调用 eachover 的析构函数是有问题的,因为这可能会导致未定义的行为。
例如,查看以下情况:
- 正在删除
v
Vertex
对象, - 这导致删除成员向量
m_edge
中的第 1 个Edge
, - 这导致删除
m_head
和m_tail
Vertex
, - 假设其中一个是
v
,那么v
析构函数中的下一个循环将尝试访问已删除的数据!!
最好的情况下,您的程序会出现段错误;在最坏的情况下...谁知道呢。。。
你的设计还不错。然而,它的问题在于你不能清楚地定义所有权(这可能有助于知道谁应该摧毁谁(。
事实上,假设一个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;
}
现场示例