У меня есть класс Dag (направленный ациклический граф), который содержит вектор необработанных указателей на объекты класса Node. Этот вектор называется m_roots
и состоит из всех узлов, которые не имеют потомков. (Но они могут иметь до двух родителей) Объекты Node образуют своего рода двоичные деревья.
Атрибуты-члены узлов:
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()
{
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.
Тот факт, что он сломает это рано, делает маловероятным, что это проблема циклов в Даге …
У меня также есть аргумент функции __in_charg, который <optimized out>
(несмотря на -O0). Я не уверен, что это значит, но кажется, что Node* dummyD=m_dad;
не читается …
Я ищу причину, почему это не работает, недостаток в логике … Я знаю, что это можно сделать с помощью shared_ptr
для мамы и папы и weak_ptr
для потомков.
Замечания: Номенклатура родитель / потомок в определенной степени специфична для конкретной области. Здесь я использую это в «биологическом» смысле: у каждого человека есть только одна мама и один папа, но может иметь от 0 до n потомков.
в 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
«s m_offspring
не равно this
, (И то же самое для m_mom
.)
Не прямое решение, но я думаю, что еще более полезно: если это возможно, полностью избавиться от всех упомянутых проблем с помощью умных указателей
Node
{
int m_indiv;
Node * m_dad;
Node * m_mom;
std::vector<std::shared_ptr<Node> > m_offsprings;
int m_generat;
}
Нет, если узел разрушен (- и он последний указывает на потомков), все деструкторы потомков автоматически вызываются рекурсивно. Таким образом, нет необходимости писать дальнейший подверженный ошибкам код.
m_roots [0] и m_roots [1] делят одного и того же отца.
Когда вы удаляете Node m_roots [0], удаляются его папа и мама, а также вся их семья. Таким образом, m_roots [1] становится сиротой.