DAG 析构函数出错

Question

我有一个 Dag class（有向无环图），其中包含指向 class 节点对象的原始指针向量。该向量称为 m_roots，由所有没有后代的节点组成。（但它们最多可以有两个父节点）Node 对象形成了某种二叉树。 Nodes的成员属性为：

int m_indiv;
Node * m_dad;
Node * m_mom;
std::vector<Node * > m_offsprings;
int m_generat;

所以虽然结构是无环的，但我有两个方向的指针。 Dag 构造函数启动一个循环，从映射中包含的数据创建节点。这是经常出现的部分：

void Node::recNode(const map<int, pair<int, int> > &mapPed, map<int, Node * > &mapDup, const vector <int> &sampleListe, vector<Node * > &sample)
{

    if (find (sampleListe.begin(), sampleListe.end(), this->m_indiv) != sampleListe.end()) {
        sample.push_back(this);
    }
    pair<int, int> parents;


    if (parents.first!=0) { //0 is a reserved integer for missing data, pointer stay to NULL (nullptr)
        if (mapDup.find(parents.first) == mapDup.end() || !(mapDup[parents.first])) {
            m_dad=new Node(parents.first);
            if (mapDup.find(parents.first) != mapDup.end()) { 
                mapDup[parents.first]=m_dad;
            }
            m_dad->recNode(mapPed, mapDup, sampleListe, sample);
        }
        else {
            m_dad=mapDup[parents.first];
        }
        m_dad->m_offsprings.push_back(this); //add the pointer to this node in the dads list of offspring
    }

    //do the same for the second parent
    if (parents.second!=0) {
        if (mapDup.find(parents.second) == mapDup.end() || !(mapDup[parents.second]) ) {
            m_mom=new Node(parents.second);
            if (mapDup.find(parents.second) != mapDup.end()) {
                mapDup[parents.second]=m_mom;
            }
        m_mom->recNode(mapPed, mapDup, sampleListe, sample);
        }
        else {
            m_mom=mapDup[parents.second];
        }
        m_mom->m_offsprings.push_back(this); //add the pointer to this node in the moms list of offspring
    }

}

我的 Dag 析构函数启动递归销毁：

Dag::~Dag()
{
    for (int i(0); i<m_roots.size();++i) {
        delete m_roots[i];
    }
}

节点析构函数应该进行实际的销毁：

Node::~Node()        

{
    if(m_dad) {
        Node* dummyD=m_dad;
        for (int i(0); i<m_dad->m_offsprings.size();++i) {
            if (m_dad->m_offsprings[i]) {
                m_dad->m_offsprings[i]->m_dad=nullptr;
            }
        }
        delete dummyD;
    }
    if(m_mom) {
        Node* dummyM=m_mom;
        for (int i(0); i<m_mom->m_offsprings.size();++i) {
            if (m_mom->m_offsprings[i]) {
                m_mom->m_offsprings[i]->m_mom=nullptr;
            }
        }
        delete dummyM;
    }

}

出于某种原因，这不起作用：我遇到段错误。对应的Valgrind错误为：

InvalidRead                                     Invalid read of size 8
                                                Call stack:
/usr/include/c++/4.8/bits/stl_vector.h  646     0x411734: Node::~Node()
~/Dag.cpp                               138     0x409E98: Dag::~Dag()
~/main.cpp                              114     0x41062B: main
            Address 0x18 is not stack'd, malloc'd or (recently) free'd

逐行调试时，它在以下行中断：

for (int i; i<m_dad->m_offsprings.size();++i) {

第一次迭代后。（在第一次调用 ~Dag() 和第一次调用 ~Node() 期间）。 for 循环中断处的 i 刚刚从 0 变为 1。它早早打破这一事实使得它不太可能是 Dag 中的循环问题...... 我还有一个“__in_charg”函数参数，它是 <optimized out>（尽管 -O0）。我不确定这是什么意思，但似乎 Node* dummyD=m_dad; 没有被读取...

我正在寻找它不起作用的原因，逻辑中的缺陷...我知道可以使用 shared_ptr 来完成妈妈和爸爸，使用 weak_ptr 来完成后代。

注意： 术语 parent/offspring 在某种程度上是特定领域的。这里我在"biological"意义上使用它：每个人只有一个妈妈和一个爸爸，但可以有 0 到 n 个后代。

Answer 1

不是直接的解决方案，但我想更有帮助：如果可能的话，通过使用智能指针完全摆脱所有提到的问题

Node
{
    int m_indiv;
    Node * m_dad;
    Node * m_mom;
    std::vector<std::shared_ptr<Node> > m_offsprings;
    int m_generat;
}

不，如果一个节点被析构（——它是最后一个指向后代的节点），所有后代析构函数都会自动递归调用。因此，无需再编写容易出错的代码。

Answer 2

m_roots[0] 和 m_roots[1] 同父异母。当您删除节点 m_roots[0] 时，它的父亲和母亲以及它们的整个 "family" 都会被删除。因此，m_roots[1]成为孤儿。

Answer 3

在Node::~Node()函数中，好像this是m_offsprings中的一个。所以在

的第一次迭代之后

for (int i(0); i<m_dad->m_offsprings.size();++i) {
    if (m_dad->m_offsprings[i]) {
        m_dad->m_offsprings[i]->m_dad=nullptr;
    }
}

this->m_dad 变为 nullptr。之后你试图在 m_dad->m_offsprings.size().

中取消引用它

要解决此问题，请检查当前 m_dad 的 m_offspring 的地址是否不等于 this。（m_mom 也一样。）

DAG 析构函数出错

Error in DAG destructor

c++

destructor

directed-acyclic-graphs