Связанный список: как реализовать деструктор, конструктор копирования и оператор присваивания копирования?

Это мой код на С++:

#include <iostream>

using namespace std;

typedef struct Node
{   
    int data;
    Node* next;
}Node;

class LinkedList
{
private:
    Node* first;
    Node* last;
public:
    LinkedList() {first = last = NULL;};
    LinkedList(int A[], int num);
    ~LinkedList();

    void Display();
    void Merge(LinkedList& b);
  
};

// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
{   
    Node* t = new Node;
    if (t == NULL)
    {
        cout << "Failed allocating memory!" << endl;
        exit(1);
    }
    t->data = A[0];
    t->next = NULL;
    first = last = t;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        if (t == NULL)
        {
            cout << "Failed allocating memory!" << endl;
            exit(1);
        }
        t->data = A[i];
        t->next = NULL;
        
        last->next = t;
        last = t;
    }
}

// Deleting all Node in Linked List
LinkedList::~LinkedList()
{
    Node* p = first;
    Node* tmp;

    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        delete tmp;
    }
}

// Displaying Linked List
void LinkedList::Display()
{
    Node* tmp;

    for (tmp = first; tmp != NULL; tmp = tmp->next)
        cout << tmp->data << " ";
    cout << endl;    
}

// Merge two linked list
void LinkedList::Merge(LinkedList& b)
{
    // Store first pointer of Second Linked List
    Node* second = b.first;
    Node* third = NULL, *tmp = NULL;

    // We find first Node outside loop, smaller number, so Third pointer will store the first Node
    // Then, we can only use tmp pointer for repeating process inside While loop
    if (first->data < second->data)
    {
        third = tmp = first;
        first = first->next;
        tmp->next = NULL;
    }
    else
    {
        third = tmp = second;
        second = second->next;
        tmp->next = NULL;
    }

    // Use while loop for repeating process until First or Second hit NULL
    while (first != NULL && second != NULL)
    {
        // If first Node data is smaller than second Node data
        if (first->data < second->data)
        {
            tmp->next = first;
            tmp = first;
            first = first->next;
            tmp->next = NULL;
        }
        // If first Node data is greater than second Node data
        else
        {
            tmp->next = second;
            tmp = second;
            second = second->next;
            tmp->next = NULL;
        }
    }

    // Handle remaining Node that hasn't pointed by Last after while loop
    if (first != NULL)
        tmp->next = first;
    else
        tmp->next = second;

    // Change first to what Third pointing at, which is First Node
    first = third;    

    // Change last pointer from old first linked list to new last Node, after Merge
    Node* p = first;
    while (p->next != NULL)
    {
        p = p->next;
    }    
    last = p;
    
    // Destroy second linked list because every Node it's now connect with first linked list
    // This also prevent from Double free()
    b.last = NULL;
    b.first = NULL;
}

int main()
{
    int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
    int arr2[] = {2, 6, 10, 16, 18, 22, 24};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    
    LinkedList l1(arr1, size1);
    LinkedList l2(arr2, size2);

    l1.Display();
    l2.Display();
    
    // Merge two linked list, pass l2 as reference
    l1.Merge(l2);
    l1.Display();

    return 0;
}

Я новичок в C++, и в этом коде я практикую объединение двух связанных списков. Это на самом деле отлично работает. Я успешно объединил два связанных списка в отсортированном порядке.

См. также:  Как масштабировать экспресс-сервер node, который передает файлы?

Но есть люди, которые говорят, что я должен следовать Правилу трех в C++. Какие реализуют: Деструктор, Конструктор копирования и Оператор присваивания копирования.

Я смотрел много видео об этом. Я понимаю, что это в основном обработка Shallow Copy, особенно когда мы не хотим, чтобы два разных объекта указывали на один и тот же адрес памяти. Но моя проблема в том, что я до сих пор не знаю, как реализовать это в классе, который работает со связанным списком, как мой код выше.

Кто-то сказал, что в моем main() этот код: l1.Merge(l2); как-то неверен, потому что у меня нет явного конструктора копирования.

И если вы посмотрите на мою функцию Merge() в последней строке, если бы я этого не сделал: b.last = NULL; и b.first = NULL; , которые просто уничтожают указатель второго связанного списка, компилятор выдает мне предупреждение: Double free() обнаружено.

Итак, я думаю, что мой вопрос:

  1. Как этот код: l1.Merge(l2); может иметь какое-то отношение к конструктору копирования?
  2. Произошло ли Double free() из-за того, что я не применяю правило трех? Если да, то как их решить?
  3. Как написать правило трех на основе моего кода? Когда или как их использовать?
  4. Основываясь на этом Кодексе, что-то не так? Нужна ли мне по-прежнему Правило трех, если моя программа хочет только объединить связанный список?

Спасибо. Я надеюсь, что кто-то может объяснить мне, как будто мне 10 лет. и надеюсь, что кто-то может написать мне код.

Как написать правило трех на основе моего кода? Когда или как их использовать? Каждый раз, когда ваш класс выделяет память, которой он владеет, и использует необработанные указатели, вам нужно будет следовать правилу 3 или 5.   —  person Kevinkun    schedule 16.07.2021

См. также:  Как использовать указатель функции для возврата указателя функции?

Двойное освобождение() произошло из-за того, что я не применяю правило трех? Да, двойное освобождение является вероятным результатом невыполнения правила трех.   —  person Kevinkun    schedule 16.07.2021

@drescherjm Можете ли вы быть более конкретным? Моего конструктора по умолчанию недостаточно для этого?   —  person Kevinkun    schedule 16.07.2021

@Kevinkun l1 = l2; — и — LinkedList l3 = l1; — Вы пробовали этот простой тест? Ваша программа main, похоже, избегает необходимости проверять копирование и присваивание. Вы увидите, что все разваливается или работает правильно, просто написав эти тестовые строки.   —  person Kevinkun    schedule 16.07.2021

@Kevinkun Кстати, вы должны были внедрить правило трех способов до написания Merge или любой подобной функции. Может быть, вставить и удалить, но все более сложное следует отложить после того, как вы подтвердите, что копирование, присваивание и удаление (правило 3) работают правильно. Прямо сейчас вы добавляете функции поверх неисправного фундамента. В вашем случае, сразу после того, как вы внедрили конструктор для вставки элементов массива в список, следующим делом будет реализация копирования и присваивания (и уничтожения).   —  person Kevinkun    schedule 16.07.2021

Возможная реализация состоит в том, чтобы просто явно удалить оператор копирования и оператор присваивания, если они вам не нужны. Таким образом, если ваш код позже попытается их использовать, вы получите ошибку времени компиляции. И поскольку вы уничтожаете l2 в merge, я бы использовал ссылку &&, чтобы сделать это явным.   —  person Kevinkun    schedule 16.07.2021

Вы должны реализовать деструктор. Вам не нужно реализовывать два других, вы можете сделать их удаленными вместо этого, и в этом случае ваши связанные списки не будут копироваться (и компилятор будет кричать на вас, если вы случайно попытаетесь их скопировать).   —  person Kevinkun    schedule 16.07.2021

См. также:  кодер по умолчанию для объекта pojo в Apache Beam

@SergeBallesta Можете ли вы объяснить, почему я должен использовать &&? и как его использовать?   —  person Kevinkun    schedule 16.07.2021

stackoverflow.com/questions/12606574/   —  person Kevinkun    schedule 16.07.2021

Понравилась статья? Поделиться с друзьями:
IT Шеф
Комментарии: 2
  1. Kevinkun

    Но моя проблема в том, что я до сих пор не знаю, как реализовать [Правило трех] в классе, который работает со связанным списком, как мой код выше.

    Вы просто реализуете конструктор копирования и оператор присваивания копии для итерации входного списка, создания копии каждого узла и вставки их в целевой список. У вас уже есть работающий деструктор. В случае оператора присваивания копии обычно можно использовать идиому копирования-подкачки, чтобы реализовать его с помощью конструктора копирования для избегайте повторений.

    Кто-то сказал, что в моем main() этот код: l1.Merge(l2); как-то неверен, потому что у меня нет явного конструктора копирования.

    Тогда вам неправильно сказали. Ваш код Merge() не имеет ничего общего с конструктором копирования.

    И если вы посмотрите на мою функцию Merge(), в последней строке, если я не сделал этого: b.last = NULL; и b.first = NULL;, которые просто уничтожают указатель второго связанного списка, компилятор выдает мне предупреждение: Double free() detected.

    Правильный. Поскольку вы перемещаете узлы из входного списка в целевой список, вам нужно сбросить входной список, чтобы он больше не указывал на перемещенные узлы. В противном случае деструктор входного списка попытается их освободить, как и деструктор целевого списка.

    Как этот код: l1.Merge(l2); может иметь какое-то отношение к конструктору копирования?

    Это не имеет к этому никакого отношения.

    Double free() произошло из-за того, что я не применяю правило трех?

    Не в вашем конкретном примере, поскольку вы не выполняете никаких операций копирования. Но, в целом, несоблюдение правила трех может привести к двойному освобождению, да.

    Как написать правило трех на основе моего кода?

    См. код ниже.

    Нужна ли мне по-прежнему Правило трех, если моя программа хочет только объединить связанный список?

    Нет. Только когда вы хотите сделать копии списков.

    С учетом сказанного, вот реализация, которая включает Правило Трех:

    #include <iostream>
    #include <utility>
    
    struct Node
    {
        int data;
        Node *next;
    };
    
    class LinkedList
    {
    private:
        Node *first;
        Node *last;
    public:
        LinkedList();
        LinkedList(const LinkedList &src);
        LinkedList(int A[], int num);
        ~LinkedList();
    
        LinkedList& operator=(const LinkedList &rhs);
    
        void Display() const;
        void Merge(LinkedList &b);
    };
    
    // Create Linked List using default values
    LinkedList::LinkedList()
        : first(NULL), last(NULL)
    {
    }
    
    // Create Linked List using Array
    LinkedList::LinkedList(int A[], int n)
        : first(NULL), last(NULL)
    {
        Node **p = &first;
    
        for (int i = 0; i < n; ++i)
        {
            Node *t = new Node;
            t->data = A[i];
            t->next = NULL;
    
            *p = t;
            p = &(t->next);
    
            last = t;
        }
    }
    
    // Create Linked List by copying another Linked List
    LinkedList::LinkedList(const LinkedList &src)
        : first(NULL), last(NULL)
    {
        Node **p = &first;
    
        for (Node *tmp = src.first; tmp; tmp = tmp->next)
        {
            Node* t = new Node;
            t->data = tmp->data;
            t->next = NULL;
    
            *p = t;
            p = &(t->next);
    
            last = t;
        }
    }
    
    // Deleting all Node in Linked List
    LinkedList::~LinkedList()
    {
        Node *p = first;
    
        while (p)
        {
            Node *tmp = p;
            p = p->next;
            delete tmp;
        }
    }
    
    // Update Linked List by copying another Linked List
    LinkedList& LinkedList::operator=(const LinkedList &rhs)
    {
        if (&rhs != this)
        {
            LinkedList tmp(rhs);
            std::swap(tmp.first, first);
            std::swap(tmp.last, last);
        }
        return *this;
    }
    
    // Displaying Linked List
    void LinkedList::Display() const
    {
        for (Node *tmp = first; tmp; tmp = tmp->next)
            std::cout << tmp->data << " ";
        std::cout << std::endl;
    }
    
    // Merge two linked list
    void LinkedList::Merge(LinkedList& b)
    {
        if ((&b == this) || (!b.first))
            return;
    
        if (!first)
        {
            first = b.first; b.first = NULL;
            last = b.last; b.last = NULL;
            return;
        }
    
        // Store first pointer of Second Linked List
        Node *second = b.first;
        Node *third, **tmp = &third;
    
        // We find first Node outside loop, smaller number, so Third pointer will store the first Node
        // Then, we can only use tmp pointer for repeating process inside While loop
        // Use while loop for repeating process until First or Second hit NULL
        do
        {
            // If first Node data is smaller than second Node data
            if (first->data < second->data)
            {
                *tmp = first;
                tmp = &(first->next);
                first = first->next;
            }
            // If first Node data is greater than second Node data
            else
            {
                *tmp = second;
                tmp = &(second->next);
                second = second->next;
            }
            *tmp = NULL;
        }
        while (first && second);
    
        // Handle remaining Node that hasn't pointed by Last after while loop
        *tmp = (first) ? first : second;
    
        // Change first to what Third pointing at, which is First Node
        first = third;  
    
        // Change last pointer from old first linked list to new last Node, after Merge
        Node *p = first;
        while (p->next)
        {
            p = p->next;
        }   
        last = p;
        
        // Destroy second linked list because every Node it's now connect with first linked list
        // This also prevent from Double free()
        b.first = b.last = NULL;
    }
    
    int main()
    {
        int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
        int arr2[] = {2, 6, 10, 16, 18, 22, 24};
        int size1 = sizeof(arr1) / sizeof(arr1[0]);
        int size2 = sizeof(arr2) / sizeof(arr2[0]);
        
        LinkedList l1(arr1, size1);
        LinkedList l2(arr2, size2);
        LinkedList l3(l1);
        LinkedList l4;
    
        l1.Display();
        l2.Display();
        l3.Display();
        l4.Display();
        
        // Merge two linked list, pass l2 as reference
        l3.Merge(l2);
        l4 = l3;
    
        l1.Display();
        l2.Display();
        l3.Display();
        l4.Display();
    
        return 0;
    }
    

    Демо

    Вот это да. Спасибо за ваше объяснение! person Kevinkun; 16.07.2021

    Итак, для этой функции: LinkedList::LinkedList(const LinkedList &src) и LinkedList& LinkedList::operator=(const LinkedList &rhs) это будет выполняться только в том случае, если я выполню копирование из существующего объекта в новый объект в своем коде? Нравится l1 = l2 или LinkedList l2(l1) ? person Kevinkun; 16.07.2021

    Да, это конструктор копирования и оператор присваивания копии, они вызываются только при копировании. И если вы действительно хотите быть тщательным, рассмотрите Правило пяти, которое добавляет конструктор перемещения и оператор присваивания перемещения для кражи ресурсов без создания копий. Семантика перемещения была введена в C++11. person Kevinkun; 16.07.2021

  2. Kevinkun

    В этом коде применено несколько сомнительных практик, а также есть ошибка.

    Во-первых, баг. Когда вы создаете список, он newсобирает все свои узлы и отслеживает их с помощью указателей. Когда вы назначаете список другому, вы буквально копируете значения указателя. Мало того, что теперь вы потеряли узлы назначенного списка (потому что вы перезаписали их) и получили утечку памяти (потому что теперь нет указателя, указывающего на выделенные узлы), вы также теперь имеете одинаковые указатели в двух разных списках, указывающие на те же узлы. Когда списки уничтожаются, оба из них пытаются delete своих узлов, и в итоге вы освобождаете одну и ту же память дважды. Юк.

    Решение этой ошибки заключается в реализации оператора присваивания.

    Затем сомнительные практики:

    1. using namespace std; (Почему использование пространства имен std считается плохой практикой? )
    2. Вы назначаете члены LinkedList в теле конструктора вместо того, чтобы передавать значения непосредственно их конструктору в списке инициализации. (Что это за странный член двоеточия ( : ) синтаксис в конструкторе?)
    3. Объявление параметра массива (int[]) — это объявление указателя. Просто знайте это.
    4. new не может вернуть NULL! Бесполезно проверять его возвращаемое значение. Если он не может выделить, он просто выдаст исключение.
    5. NULL — неподходящая константа для использования. Вы можете использовать nullptr, это эквивалент C++ NULL, за исключением того, что он безопасен для типов.
    6. Ручное управление памятью с помощью new и delete сложно сделать правильно (как вы сами поняли). Возможно, вам будет интересно использовать std::unique_ptr или std::shared_ptr, чтобы облегчить нагрузку. Они бы поймали жука.

    Теперь, пожалуйста: не пишите на C++, как на C с классами. Я понимаю, что вы, возможно, не сталкивались со всеми функциями, которые я здесь представил, но в любом случае теперь вы о них знаете :)

    Спасибо за сомнительные практики! Я понимаю с вашим объяснением об утечках памяти. Но какой код создания является ошибкой? Вы имеете в виду, что этот код создания неверен: LinkedList l1(arr1, size1); и LinkedList l2(arr2, size2);? и какой именно код я должен использовать с оператором присваивания? person Kevinkun; 16.07.2021

    Потому что код на самом деле работает отлично. Я обрабатываю утечки памяти с помощью Передачи по ссылке и уничтожаю l2, назначая b.first = NULL и b.last=NULL, поэтому при вызове деструктора он не будет дважды освобождаться. Моя проблема в том, что я хочу знать, может быть, есть хорошая практика в моем коде с использованием правила трех? person Kevinkun; 16.07.2021

    Для комментария 1: ошибка, о которой я говорил, возникает, когда вы назначаете LinkedList. Несмотря на то, что вы не определили оператор присваивания, компилятор определил для вас его, который, как оказалось, делает не то, что надо. (Примечание: вы не используете оператор присваивания в опубликованном вами коде. Вот почему в некоторых комментариях предлагалось пометить его как deleted (кстати, что-то совершенно отличное от освобождения памяти), поэтому он никогда не будет вызываться. Однако ошибка все еще существует, она просто не представился). person Kevinkun; 16.07.2021

    Для комментария 2: использование правила трех обычно является хорошей практикой, когда вы не можете следовать правилу нуля. То есть, когда компилятор предоставляет конструкторы и операторы присваивания, они не будут делать то, что вам нужно. Суть здесь в том, что чем меньше кода вы пишете, тем лучше, поэтому позвольте компилятору написать его за вас, если можете. Отредактировано: ответ был частично неправильным, потому что я думал, что вы говорите о какой-то другой части кода. person Kevinkun; 16.07.2021

    Кроме того, вот совет: вы также можете вызвать конструктор для Node, когда вы new его. Компилятор сгенерировал для вас тот, который делает то, что вы хотите в этом случае (посмотрите агрегатную инициализацию). person Kevinkun; 16.07.2021

    @Kevinkun Моя проблема в том, что я хочу знать, может быть, есть хорошая практика в моем коде с использованием правила трех? — Я думаю, вы не видели мой комментарий в основном разделе. Простое задание, и ваш связанный список развалится. Единственный способ предотвратить это — запретить копирование и присваивание во время компиляции. Кроме того, ваша программа main, которую вы опубликовали, не использовала ваш код в достаточной степени, чтобы обнаружить эти ошибки — она ​​в основном направлена ​​​​на то, чтобы не находить проблемы, и вы не должны тестировать эти проблемы таким образом. person Kevinkun; 16.07.2021

    @PaulMcKenzie Я видел твой комментарий. Итак, если в моей main программе нет кода, выполняющего копирование или присваивание, как вы сказали, мне не нужно реализовывать правило трех? или, исходя из моего кода, есть ли какая-то часть, которую я могу реализовать с помощью правила трех? person Kevinkun; 16.07.2021

    Конечно. Если вы не застрелитесь, вполне нормально держать пистолет наведенным на ногу. Но вам следует избегать этого. person Kevinkun; 16.07.2021

    Вам необходимо обеспечить это во время компиляции, явно объявив конструктор копирования и оператор присваивания с помощью спецификатора = delete. Если вы этого не сделаете, то ваш код легко развалится в местах, которых вы никогда не ожидаете. Например, если вы поместите свой класс LinkedList в контейнер, который выполняет копирование за кулисами (например, std::vector), у вас будут проблемы. Если вы передаете или возвращаете значение, у вас проблемы. Если компилятор сам должен сделать копию, а вы даже не подозреваете об этом, у вас проблемы. Таким образом, вы либо делаете класс копируемым, либо отключаете копирование. person Kevinkun; 16.07.2021

    Не используйте unique_ptr или shared_ptr для реализации связанного списка, если только вам не нравится переполнение стека. person Kevinkun; 16.07.2021

    @PaulMcKenzie Хорошо. Но, последний вопрос, Люди сказали, что я должен следовать Правилу Трех для моего кода выше. Дело в том, что я не понимаю, какой код я неправильно реализовал. Потому что все, что я знаю, это то, что код работает идеально. Итак, если есть, может быть, вы можете указать, какую часть моего кода я должен реализовать с помощью конструктора копирования или оператора присваивания? person Kevinkun; 16.07.2021

    @Kevinkun — Что, если я решу использовать ваш класс связанного списка? Вы не представляете, как я буду его использовать. Он должен быть безопасно копируемым и назначаемым, иначе он в основном бесполезен. Опять же, ваша программа main склонна не показывать ошибки. Любой может написать ошибочные классы и написать код, который не показывает скрытых ошибок. Как только кто-то, независимый от исходного программиста, начинает использовать класс, все ошибки выявляются. person Kevinkun; 16.07.2021

    Я уже написал код: l1 = l2;. Только это само по себе показывает ошибки. Или LinkedList l3 = l1; или std::vector<LinkedList> vL; vL.push_back(l1); person Kevinkun; 16.07.2021

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: