我的 stack pop 实现会泄漏内存吗？

Question

我这样做是为了学习。据我了解，每个 new 都需要有相应的 delete。我的 pop() 定义是否导致内存泄漏？它弹出 head，但我不知道如何只删除 head。

根据我的理解，它可能没有内存泄漏，但我不确定（Valgrind 没有发现任何东西）：

将head指针保存在temp指针中。
点head到head->next。
return temp.data.
} 块结束时自动释放内存。

但据我了解，我真正真正想做的是调用 delete head。因为head在堆中，弹出时需要删除。但我也在想，因为它是一个递归数据结构，如果我调用 delete head，我将递归删除所有内容，就像我在 ~Node() 中定义的那样，对吗？如果我想像这样Node* temp = head这样的temp点保存head，我不就复制一份吗？所以我尝试使用Node*temp = std::move(head); head = std::move(temp->next); delete temp;，然后弹出错误free(): double free detected in tcache 2，这是什么意思？在这一点上，我不知道如何进行。我到处搜索，找不到解决方案。试过了，没有成功：

将head指针保存在temp指针中。
保存 temp->data 中的 data。
点head到head->next。
将temp->next设置为nullptr？
- 原因temp持有递归节点
- 如何只提取 head 而没有 next 中的那些节点？
delete temp删除原来的head?
return data.

我知道如何使用 unique_ptr 来实现它，它解决了我所有的问题，让我无后顾之忧。但我需要知道如何手动执行此操作。

template<typename Data>
class ListStack {
public:
    ListStack(): head{nullptr} {}

    ~ListStack();

    [[nodiscard]] bool isEmpty() const;

    void push(Data const &data);

    Data pop();

private:
    struct Node {
        Data data;
        Node* next;

        explicit Node(Data const &data, Node* next=nullptr) : data{data}, next{next} {}

        ~Node() { delete next; }
    };

    Node* head;
};

template<typename Data>
bool ListStack<Data>::isEmpty() const {
    return head == nullptr;
}

template<typename Data>
void ListStack<Data>::push(Data const &data) {
    head = new Node(data, head);
}

template<typename Data>
Data ListStack<Data>::pop() {
    if (isEmpty()) {
        throw std::out_of_range("ListStack underflow");
    }
    Node* temp = head;
    head = head->next;
    return temp->data;
}

template<typename Data>
ListStack<Data>::~ListStack() { delete head; }

最后一次尝试使用递归删除，为什么错误 free(): invalid pointer？

template<typename Data>
Data ListStack<Data>::pop() {
    if (isEmpty()) {
        throw std::out_of_range("ListStack underflow");
    }
    Node* temp = new Node(head->next->data, head->next->next);
    Data data = head->data;
    delete head;
    head = temp;
    return data;
}

使用unique_ptr的工作示例，如果有任何错误请告诉我：

template<typename Data>
Data ListStack<Data>::pop() {
    if (isEmpty()) {
        throw std::out_of_range("ListStack underflow");
    }
    Data data = head.get()->data;

    // ~Node() and ~ListStack() are not implemented, using default.
    // head and next are std::unique_ptr<Node>
    head = std::move(head.get()->next);
    // here the original head has no one owns it, so it gets freed automatically.
    return data;
}

Answer 1

我画图搞定了

Class 在 C++ 中只是一个数组。比如我实现的Node，如果Data是int，next是一个指针，也是一个int。 64bit int是8bytes，也就是说每填充一个head就是16byte（我打印了sizeof(head)，就是16，证明了这一点）

head
-----------
|Data|next| =>
-----------
-----------
|Data|next| =>
-----------
-----------
|Data|NULL|
-----------
tail

我想要的结果。并删除头数组：

original head, set next to nullptr, can be deleted safely
-----------
|Data|NULL|
-----------

temp, hold the new head
-----------
|Data|next| =>
-----------
-----------
|Data|NULL|
-----------
tail

这是代码：

template<typename Data>
Data ListStack<Data>::pop() {
    if (isEmpty()) {
        throw std::out_of_range("ListStack underflow");
    }
    // copy the next pointer to a local varialbe temp pointer
    Node* temp = head->next;
    Data data = head->data;

    // this step separated head from the rest
    head->next = nullptr;

    // to be popped head gets deleted, conform to one new one delete principle
    delete head;

    // copy temp pointer to head
    head = temp;
    return data;

    // all locally allocated memory get freed here
}

我的 stack pop 实现会泄漏内存吗？

Is my implementation of stack pop leaking memory?

c++

memory-leaks