Проблема с конструктором, деструктором и оператором = в связанном списке

Question

Итак, у меня проблема с успешной сборкой кода, но после запуска в Visual Studio он останавливается с сообщением «Недостаточно системных ресурсов для завершения запрошенной службы». Код в основном создает связанный список, и я реализую класс Set, который создает список и выполняет над ним основные операции c.

Я считаю, что это проблема с моим конструктором копирования, деструктором и оператором = , Ниже приведен код:

main. cpp

#include <iostream>
#include "Set.h"

using namespace std;

int  main()
{
    Set a;
    a.insert("aa");
    a.insert("bb");
    a.insert("cc");
    a.insert("dd");

    Set b;
    b.insert("ee");
    b.insert("ff");

    Set c;
    Set c(b);
    cout << "C is " << endl;
    c.dump();
    cout << endl;
    c = a;
    cout << "C is " << endl;
    c.dump();

Set.h

class Set
{
public:
    Set();
    bool empty() const;
    int size() const;
    bool insert(const ItemType& value);
    bool erase(const ItemType& value);
    bool contains(const ItemType& value) const;
    bool get(int pos, ItemType& value) const;
    void swap(Set& other);
    void dump();

    ~Set();
    Set(const Set& other);
    Set& operator=(Set other);

private:
    struct Node
    {
        ItemType data;
        struct Node* next;
        struct Node* prev;

    }m_dummy;

    Node *m_dummyPtr;
    int m_size;

};

Set. cpp // копировать конструктор, деструктор и только оператор =

Set::~Set()
{
    Node* current = m_dummyPtr->next;
    Node* next;
    for (int i = 0; i < m_size;i++)
    {
        next = current->next;;
        delete current;
        current = next;
    }
    m_dummyPtr->next = nullptr;
    m_dummyPtr->prev = nullptr;

}

Set::Set(const Set& other)
{
    m_size = other.m_size;
    Node* p = other.m_dummyPtr->next;

    m_dummyPtr = &m_dummy;
    m_dummyPtr->data = {};
    m_dummyPtr->next = m_dummyPtr;
    m_dummyPtr->prev = m_dummyPtr;

    if (m_size == 0)
        ;
    else
    {
        for (int i = 0;i < m_size;i++)
        {
            insert(p->data);
            p = p->next;
        }
    }
}

Set& Set::operator=(Set other)
{
    if (this != &other) {
        swap(other);
    }
    return *this;
}

Установить реализацию функции вставки

bool Set::insert(const ItemType& value)
{
    if (m_size == 0)
    {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->prev = &m_dummy;
        newNode->next = &m_dummy;

        m_dummy.next = newNode;
        m_dummy.prev = newNode;

        m_size++;
        return true;
    }
    else if (contains(value))
    {
        return false;
    }
    else
    {
        Node* newNode1 = new Node;
        Node* p = m_dummy.prev;
        m_dummy.prev = newNode1;
        newNode1->data = value;
        newNode1->next = &m_dummy;
        newNode1->prev = p;
        p->next = newNode1;
        m_size++;
        return true;
    }
}

Answer 1

Проблема с вашим конструктором копирования. Чтобы увидеть проблему, полезно иметь документацию по другим вашим функциям. В частности:

/**
 * Inserts `value` into `*this`, but only if `*this` does not already contain `value`.
 * Side effect: if `value` is inserted, the size is updated.
 */
bool Set::insert(const ItemType& value)

Этот побочный эффект актуален! Посмотрите, что делает ваш конструктор копирования. Сначала он устанавливает размер в соответствии с предполагаемым размером final , затем он вызывает insert() для каждого элемента для вставки. Каждый такой вызов увеличивает размер сверх ожидаемого окончательного размера . В лучшем случае вы видите, что m_size является удвоенным числом узлов в списке (до тех пор, пока копия не будет скопирована, когда размер станет как минимум в три раза больше, чем должно быть, и т. Д.). Однако, 1010 *

ситуация хуже чем это. L oop, управляющий вставками, будет выполняться m_size раз, и каждая итерация потенциально увеличивается m_size. Ваша настройка в основном следующая (я вставил insert() и удалил некоторый код, чтобы сосредоточиться на проблеме):

for (int i = 0;i < m_size;i++)
    if (!contains(value))
        m_size++;

Если по какой-то причине ваша contains() функция должна была всегда завершаться с ошибкой возвращая false, вы смотрите на бесконечное l oop, так как и управляющая переменная l oop, i, и конечное условие, m_size, будут увеличиваться с каждой итерацией. Быстрая помощь при этой потенциальной проблеме - от l oop до i < other.m_size, так как размер другого не изменится. Еще лучше было бы сбросить i и l oop до p == &other.m_dummy (я не знаю, почему вы потратили место на m_dummyPtr). Тем не менее, это не решает основную проблему.

---

При написании кода у вас уже должно быть хорошее представление о том, что делает код; Вы должны быть в состоянии объяснить в Engli sh (или предпочитаемом вами человеческом языке), что должен делать код. В этом случае, похоже, что конструктор копирования намерен сначала инициализировать *this как пустой список, а затем скопировать элементы из other в *this. Так сделай это. C ++ 11 дал нам инструмент под названием делегирующий конструктор , который позволяет это делать без повторения кода, и который в этом случае может предотвратить логическую ошибку.

Set::Set(const Set& other) : Set()  // Delegate to construct an empty list
{
    // Copy the nodes of `other` to `*this`.
    Node* p = other.m_dummyPtr->next;
    if (other.m_size == 0)
        ;
    else
    {
        for (int i = 0;i < other.m_size;i++)
        {
            insert(p->data);
            p = p->next;
        }
    }
}

добавьте еще одно улучшение бесплатно. Не пишите дополнительный код для обработки особых случаев, которые бы обрабатывались сами собой. (Этот совет также относится к функции insert().) Одно из преимуществ использования сторожевого узла (поле m_dummy) заключается в том, что вам часто не приходится учитывать пустой список. Тем не менее, вы написали дополнительный код для этого случая. С помощью сторожевого узла, если ваш основной кодовый путь не может обработать пустой список, вы, вероятно, имеете логическую ошибку. Вот ваша insert() функция без проверки на пустоту.

Set::Set(const Set& other) : Set()
{
    // Copy the nodes of `other` to `*this`.
    Node* p = other.m_dummyPtr->next;
    for (int i = 0;i < other.m_size;i++)
    {
        insert(p->data);
        p = p->next;
    }
}

Это все равно будет работать, потому что тело l oop не выполняется при other.m_size == 0, поэтому нет необходимости добавлять дополнительная проверка для этого условия. Кроме того, мы можем еще больше обрезать вещи, избавившись от i:

Set::Set(const Set& other) : Set()
{
    // Copy the nodes of `other` to `*this`.
    for (Node* p = other.m_dummy.next; p != &other.m_dummy; p = p->next)
        insert(p->data);
}

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