链表 push_front 和 push_back 中的 C++ 内存泄漏

Question

我收到 valgrind 的内存泄漏错误：

 24 bytes in 1 blocks are definitely lost in loss record 1 of 11        
 at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
   by 0x413E47: pjc::list::push_back(double) (list.cpp:33)
   by 0x416371: ____C_A_T_C_H____T_E_S_T____4() (tests-list-01.cpp:86)

24 bytes in 1 blocks are definitely lost in loss record 2 of 11
   at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
   by 0x414047: pjc::list::push_front(double) (list.cpp:66)
   by 0x4192C1: ____C_A_T_C_H____T_E_S_T____10() (tests-list-01.cpp:146)

我的 .hpp 链接列表文件如下所示：

using std::size_t;

namespace pjc {

class list {
private:
    struct node {
        double val = 0;
        node* prev = nullptr;
        node* next = nullptr;
    };

    node* head = nullptr;
    node* tail = nullptr;
    size_t num_elements = 0;

public:
    list() = default;
    list(const list& rhs);
    list& operator=(const list& rhs);
    list(list&& rhs);
    list& operator=(list&& rhs);
    ~list();

    void push_back(double elem);

    void push_front(double elem); 
};

push_back()、push_front() 和链表的析构函数的定义如下所示：

list::list(const list &rhs) {
    head = tail = nullptr;
    for(node* tmp = rhs.head; tmp!=NULL; tmp=tmp->next) {
        push_back(tmp->val);
    }
    num_elements = rhs.num_elements;
}

list::~list() {
    node *T = head;
    while(T != nullptr)
    {
        node *T2 = T;
        T = T->next;
        delete T2;
    }
    head = nullptr;
    tail = nullptr;
    num_elements = 0;
}

void list::push_back(double elem) {
    node *n = new node;
    n->val = elem;
    if(tail == nullptr)
    {
        head = n;
        tail = head;
    }
    else
    {
        tail->next = n;
        n->prev = tail;
        tail = n;
    }
    num_elements++;
}

void list::push_front(double elem) {
    node *n = new node;
    n->val = elem;
    if(head == nullptr)
    {
        head = n;
        tail = head;
    }
    else
    {
        head->prev = n;
        n->next = head;
        head = n;
    }
    num_elements++;
}
list &list::operator=(const list &rhs) {
    list temp(rhs);
    std::swap(head, temp.head);
    std::swap(tail, temp.tail);
    std::swap(num_elements, temp.num_elements);
    return *this;
}

list::list(list &&rhs) {
    head = rhs.head;
    tail = rhs.tail;
    num_elements = rhs.num_elements;

    rhs.head = nullptr;
    rhs.tail = nullptr;
    rhs.num_elements = 0;
}

list &list::operator=(list &&rhs) {
    this->~list(); // Destroy our current contents
    std::swap(head, rhs.head);
    std::swap(tail, rhs.tail);
    std::swap(num_elements, rhs.num_elements);
    return *this;
}

我试过改一下析构函数，好像没问题。我真的不知道泄漏发生在哪里。

编辑：抱歉，我第一次遗漏了代码的一些重要部分。现在它应该遵循 5 的规则。

Answer 1

也许这会对你有所帮助：

template<typename T>
class List {
private:
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;

    std::size_t _size = 0;

public:

    List() = default;

    // copy constructor
    List(const List<T>& l) {
        _size = l._size;
        Node<T>* current = nullptr;
        Node<T>* previous = nullptr;
        for (std::size_t i = 0; i < l._size; ++i) {
            current = new Node<T>(l[i].data);
            current->prev = previous;
            if (previous) {
                previous->next = current;
            } else {
                head = current;
            }
            previous = current;
        }
        tail = current;
    }

    // assignment operator
    List<T>& operator=(const List<T>& l) {
        if (l.isEmpty()) {
            this->clear();
            return *this;
        }

        // keeps existing nodes intact, and only changes their value
        while (_size > l.size()) {
            Node<T>* prev = tail->prev;
            delete tail;
            prev->next = nullptr;
            tail = prev;
            --_size;
        }

        Node<T>* temp = head;
        Node<T>* tempL = l.head;
        for (std::size_t i = 0; i < _size; ++i) {
            temp->data = tempL->data;
            temp = temp->next;
            tempL = tempL->next;
        }

        while (_size < l._size) {
            this->append(tempL->data);
            tempL = tempL->next;
            ++_size;
        }

        return *this;
    }

    ~List() {
        Node<T>* temp = head;
        while (temp) {
            Node<T>* next = temp->next;
            delete temp;
            temp = next;
        }
    }

    void append(const T& value) {
        auto* temp = new Node<T>(value);
        if (!head) {
            // no head also means no tail
            head = temp;
            tail = temp;
        } else {
            tail->next = temp;
            temp->prev = tail;
            tail = temp;
        }
        ++_size;
    }

    void prepend(const T& value) {
        auto* temp = new Node<T>(value);
        temp->next = head;
        if (head) {
            head->prev = temp;
        }
        head = temp;
        ++_size;
    }
};

也就是说，您可能应该遵循三原则并实现复制构造函数和赋值运算符。

Answer 2

我在您显示的代码中没有看到任何泄漏，但您没有显示所有相关代码。

例如，您如何使用 list 对象可能是导致泄漏的原因。例如，如果您没有通过实施适当的复制和移动构造函数以及复制和移动赋值运算符来遵循 Rule of 3/5/0，那么您可能会在 copying/moving list 对象时泄漏内存。但是你没有显示那个代码，所以我们无法判断你做的是否正确。

也就是说，您的析构函数确实有一个不属于的额外 delete，并且您的 push_back() 和 push_front() 方法可以简化。

最安全的选择是简单地使用 std::list 并让它为您管理内存。但是，如果您想手动执行此操作，请尝试以下操作：

class list
{
private:
    struct node
    {
        double val;
        node* prev = nullptr;
        node* next = nullptr;

        node(double value = 0) : val(value) {}
    };

    node* head = nullptr;
    node* tail = nullptr;
    size_t num_elements = 0;

public:
    list() = default;
    list(const list &src);
    list(list &&src);
    ~list();

    list& operator=(const list &rhs);
    list& operator=(list &&rhs);

    void push_back(double elem);
    void push_front(double elem);

    void swap(list &other)
};

list::list(const list &src)
    : list()
{
    for(node *n = src.head; n != nullptr; n = n->next)
        push_back(n->val);
}

list::list(list &&src)
    : list()
{
    src.swap(*this);
}

list::~list()
{
    node *n = head;
    while (n)
    {
        node *next = n->next;
        delete n;
        n = next;
    }
}

list& list::operator=(const list &rhs)
{
    if (this != &rhs)
        list(rhs).swap(*this);
    return *this;
}

list& operator=(list &&rhs)
{
    list(std::move(rhs)).swap(*this);
    return *this;
}

void list::push_back(double elem)
{
    node *n = new node(elem);
    if (tail)
    {
        tail->next = n;
        n->prev = tail;
    }
    else
        head = n;
    tail = n;
    ++num_elements;
}

void list::push_front(double elem)
{
    node *n = new node(elem);
    if (head)
    {
        head->prev = n;
        n->next = head;
    }
    else
        tail = n;
    head = n;
    ++num_elements;
}

void list::swap(list &other)
{
    std::swap(head, other.head);
    std::swap(tail, other.tail);
    std::swap(num_elements, other.num_elements);
}

链表 push_front 和 push_back 中的 C++ 内存泄漏

C++ memory leak in linked-list push_front and push_back

c++

valgrind

memory-leaks

linked-list

doubly-linked-list