C ++ деструктор вызывается неожиданно двусвязным списком - PullRequest
Новая
       20

C ++ деструктор вызывается неожиданно двусвязным списком

0 голосов
/ 26 января 2020 
    doubly_linked_list::~doubly_linked_list()
{
    list_item* current = head;
    while (current)
    {
        list_item* next = current->Get_Next();
        delete current;
        current = next;
    }
}

Я пишу динамический c граф на C ++ с использованием двусвязного списка для сохранения узлов Graph, однако мой код продолжает давать сбой, так как он вызывает деструктор больше раз, чем должен был его вызывать Например, во время моего деструктора для графа 

    Dynamic_Graph::~Dynamic_Graph()
{
    edges.~doubly_linked_list();
    nodes.~doubly_linked_list();
}

деструктор для двусвязного списка вызывается более 2 раз, несмотря на то, что он вызывается явно дважды.

тогда у меня есть функция для вставки ребра: 

Graph_Edge* Dynamic_Graph::Insert_Edge(Graph_Node* from, Graph_Node* to)
{
    Graph_Edge* new_edge = new Graph_Edge(from, to);
    from->Get_out_Nodes().List_Insert_After(to, from->Get_out_Nodes().Get_Tail());
    to->Get_in_Nodes().List_Insert_After(from, to->Get_in_Nodes().Get_Tail());
    edges.List_Insert(new_edge);
    return new_edge;
}

после добавления узла to в список смежности узла from код необъяснимым образом вызывает деструктор для двусвязного списка и удаляет эту вставку, однако я не уверен почему.

вот заголовки для графика и связанного списка: 

class doubly_linked_list
{
private:
    list_item* head;
    list_item* tail;
public:
    doubly_linked_list() { this->head = NULL; this->tail = NULL; }
    doubly_linked_list(list_item* head){ this->head = head; this->tail = NULL; }
    ~doubly_linked_list();
    list_item* Get_Head() { return head; }
    list_item* Get_Tail() { return tail; }
    void Set_Head(list_item* h) { head = h; }
    void List_Insert(list_item* x);
    void List_Insert_After(list_item* x, list_item* y);
    void List_Delete(list_item* x);
};


class Dynamic_Graph
{
protected:
    doubly_linked_list edges;
    doubly_linked_list nodes;
public:
    Dynamic_Graph() { edges = doubly_linked_list(); nodes = doubly_linked_list(); }
    ~Dynamic_Graph();
    Graph_Node* Insert_Node(unsigned node_key);
    void Delete_Node(Graph_Node* node);
    Graph_Edge* Insert_Edge(Graph_Node* from, Graph_Node* to);
    void Delete_Edge(Graph_Edge* edge);
    Rooted_Tree* SCC() const;
    Rooted_Tree* BFS(Graph_Node* source) const;
};

любая помощь будет приветствоваться

РЕДАКТИРОВАТЬ: я удалил вызовы деструкторов, однако я все еще получаю вызов деструктора во вставке после функции, и я не уверен почему.

РЕДАКТИРОВАТЬ 2: добавление более соответствующих строк кода: 

Graph_Edge* Dynamic_Graph::Insert_Edge(Graph_Node* from, Graph_Node* to)
{
    Graph_Edge* new_edge = new Graph_Edge(from, to);
    from->Get_out_Nodes().List_Insert_After(to, from->Get_out_Nodes().Get_Tail());
    to->Get_in_Nodes().List_Insert_After(from, to->Get_in_Nodes().Get_Tail());
    edges.List_Insert(new_edge);
    return new_edge;
}

это функция, которая вызывает ошибку, когда она обращается к удаленному указателю, несмотря на то, что он не должен быть удален, она срабатывает после окончания вставки узла «to» в список смежности узлов «from». 

void doubly_linked_list::List_Insert_After(list_item* x, list_item* y)
{
    if (!y)
    {
        head = x;
        tail = x;
        return;
    }
    if (y == tail)
    {
        tail = x;
    }
    if (y->Get_Next())
    {
        y->Get_Next()->Set_Prev(x);
    }
    x->Set_Next(y->Get_Next());
    x->Set_Prev(y);
    y->Set_Next(x);
}

эта функция является функцией вставки после в двусвязном списке.

РЕДАКТИРОВАТЬ 3: я пытался исправить проблему с помощью наименьшего количества возможных функций, вот что я получил: 

#pragma once
#include < cstddef >
class List_Item
{
protected:
    List_Item* next;
    List_Item* prev;
public:
    List_Item(): next(NULL), prev(NULL) {}
    List_Item* Get_Next() { return next; }
    List_Item* Get_Prev() { return prev; }
    void Set_Next(List_Item* next) { this->next = next; }
    void Set_Prev(List_Item* prev) { this->prev = prev; }
    List_Item(const List_Item& item) : next(item.next), prev(item.prev){}
    List_Item& operator=(const List_Item& item) { this->next = item.next; this->prev = item.prev; return *this; }
};

class Doubly_Linked_List
{
protected:
    List_Item* head;
    List_Item* tail;
public:
    Doubly_Linked_List() : head(NULL), tail(NULL) {}
    ~Doubly_Linked_List();
    List_Item* Get_Head() { return head; }
    List_Item* Get_Tail() { return tail; }
    void Set_Head(List_Item* h) { head = h; }
    void Set_Tail(List_Item* t) { tail = t; }
    void insert(List_Item* item);
    void insert_after(List_Item* item, List_Item* after);
    Doubly_Linked_List(const Doubly_Linked_List& list) : head(list.head), tail(list.tail) {}
    Doubly_Linked_List& operator=(const Doubly_Linked_List& list) { this->head = list.head; this->tail = list.tail; return *this; }
};
Doubly_Linked_List::~Doubly_Linked_List()
{
    List_Item* item = head;
    while (item)
    {
        List_Item* next = item->Get_Next();
        delete item;
        item = next;
    }
}

void Doubly_Linked_List::insert(List_Item* item)
{
    item->Set_Next(head);
    if (head)
        head->Set_Prev(item);
    if (!head)
        tail = item;
    head = item;
    item->Set_Prev(NULL);
}

void Doubly_Linked_List::insert_after(List_Item* item, List_Item* after)
{
    if (!after)
    {
        head = item;
        tail = item;
        return;
    }
    if (after->Get_Next())
    {
        after->Get_Next()->Set_Prev(item);
    }
    else
    {
        tail = item;
    }
    item->Set_Next(after);
    item->Set_Prev(after);
    after->Set_Next(item);
}


#pragma once
#include "List_Item.h"
#include"Doubly_Linked_List.h"
class Graph_Node :
    public List_Item
{
protected:
    const unsigned key;
    Doubly_Linked_List in_nodes;
    Doubly_Linked_List out_nodes;
public:
    Graph_Node(unsigned key): key(key) {}
    Doubly_Linked_List Get_In_Nodes() { return in_nodes; }
    Doubly_Linked_List Get_Out_Nodes() { return out_nodes; }
};



   class Graph_Edge :
    public List_Item
{
protected:
    Graph_Node* from;
    Graph_Node* to;
public:
    Graph_Edge(Graph_Node* f, Graph_Node* t): from(f), to(t) {}
    Graph_Node* Get_From() { return from; }
    Graph_Node* Get_To() { return to; }
};

int main()
{

    unsigned node_key = 1;
    Graph_Node* from = new Graph_Node(node_key++);
    Graph_Node* to = new Graph_Node(node_key++);
    from->Get_Out_Nodes().insert_after(to, from->Get_Out_Nodes().Get_Tail());
    to->Get_In_Nodes().insert_after(from, to->Get_In_Nodes().Get_Tail());
}

1 Ответ

1 голос
/ 26 января 2020

Вы не должны вызывать деструкторы вручную. Они вызываются автоматически для вас.

Вам нужно использовать delete (который также вызывает деструктор) и только на объектах, которые вы фактически создали с вызовом new. Каждый другой объект будет уничтожен автоматически, когда будет достигнут конец его области видимости, и его деструктор будет вызван автоматически. Это также верно для членов классов.

Единственное исключение здесь, если вы использовали place-new для создания объекта или если вы намереваетесь повторно использовать его хранилище. Но вы, вероятно, не собираетесь делать что-то подобное.

Полностью удалите деструктор Dynamic_Graph. Это не нужно.

Ваш класс doubly_linked_list нарушает правило 0/3/5 . Правило гласит, что если вы определяете пользовательский деструктор, то вам также следует определить пользовательский конструктор копирования (/ перемещения) и оператор копирования (/ перемещения).

Если вы нарушаете это правило и вам случается сделать неявная или явная копия объекта этого класса, тогда вы, вероятно, будете иметь неопределенное поведение, потому что деструкторы будут вызываться дважды и пытаться удалить память дважды.

После редактирования вопроса с полным примером :

В коде, который вы сейчас показываете, деструктор для Doubly_Linked_List вызывается четыре раза (см. https://godbolt.org/z/KmStwy). Эти вызовы вызваны тем, что Get_In_Nodes и Get_Out_Nodes возвращают Doubly_Linked_List списки по значению как копии членов класса Graph_Node. Поскольку вы вызываете эти функции четыре раза в main, есть четыре Doubly_Linked_List временных объекта, которые необходимо уничтожить (что компилятор делает автоматически).

Вы неправильно реализовали Doubly_Linked_List(const Doubly_Linked_List& list) (и оператор назначения копирования) для , фактически скопировали весь список , поэтому ваша программа по-прежнему имеет неопределенное поведение. Вам необходимо реализовать операции копирования таким образом, чтобы весь список подвергался глубокому копированию, в противном случае вызов деструктора как оригинала, так и копии будет delete одинаковыми узлами.

В качестве альтернативы вы можете определить операции копирования как удаленные: 

Doubly_Linked_List(const Doubly_Linked_List& list) : head(list.head), tail(list.tail) = delete
Doubly_Linked_List& operator=(const Doubly_Linked_List& list) = delete;

, в этом случае компилятор не разрешит копирование и выдаст ошибку времени компиляции, если вы попытаетесь скопировать. Но ваша текущая реализация так же сломана, как и раньше. Вы просто скопировали то, что делают неявные операции копирования. Прочитайте ссылку о правиле 0/3/5 еще раз и внимательно, поскольку крайне важно избегать неопределенного поведения.

Тот факт, что деструктор вызывается несколько раз, сам по себе не является проблемой. Это нормально, если задействованы копии. Проблема только в том, что ваши операции копирования класса не работают. Если вы не хотите создавать копии в Get_In_Nodes и Get_Out_Nodes, тогда вместо этого возвращайте по ссылке.

Как правило, вы не должны использовать new / delete в то, что вы делаете в современном C ++. Вместо этого вы можете использовать std::make_unique и std::unique_ptr для владения указателями, и если вы это сделаете, то ни одному из ваших показанных классов не понадобятся пользовательские деструкторы (по крайней мере, не пользовательские деструкторы, которые имеют эффективное поведение, отличное от неявного), и вы всегда можете используйте правило 0, означающее, что вам также не нужно реализовывать какие-либо операции копирования.

И если это не учебное упражнение, вы не должны сначала писать свой собственный список , std::list отлично работает и почти наверняка превосходит то, что вы придумали.

...