Ошибка в деструкторе DAG

Question

У меня есть класс Dag (Направленный ациклический график), который содержит вектор необработанных указателей на объекты класса Node. Этот вектор называется m_roots и состоит из всех узлов, у которых нет потомков. (Но у них может быть до двух родителей) Объекты узла образуют двоичные деревья. Атрибутов членов Узлов являются:

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

} 

По какой-то причине это не работает: я получаю Seg Fault. Соответствующая ошибка 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()). I из цикла for, где он разбивается, только что изменился с 0 на 1. Тот факт, что он ломается на ранней стадии, маловероятен, что это проблема циклов в Dag ... У меня также есть аргумент функции __in_charg который равен <optimized out> (несмотря на -O0). Я не уверен, что это значит, но кажется, что Node* dummyD=m_dad; не читается ...

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

Примечание: Номенклатура parent/offspring несколько полезна. Здесь я использую его в «биологическом» чувстве: у каждого человека есть только одна мама и один папа, но могут иметь от 0 до n потомков.

Answer 1

В функции 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_dadm_offspring не равен this. (И то же самое для m_mom.)

Answer 2

Не прямое решение, но я думаю, еще более полезным: если каким-то образом можно полностью избавиться от всех вышеуказанных проблем, с помощью смарт-указатели

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

Нет, если узел разрушается (- и это последний, указывающий на потомков), все деструкторы потомства автоматически получают рекурсивно. Поэтому нет необходимости писать дополнительный код, подверженный ошибкам.

Answer 3

m_roots [0] и m_roots [1] поделиться тем же папой. Когда вы удаляете Node m_roots [0], его «папа и мама» будут удалены, а также вся их «семья». Таким образом, m_roots [1] становится сиротой.