C++ 中列表 class 的析构函数

Question

我是 C++ 的新手，所以才问这个问题。我有一个用 C++ 编写的单向链表的玩具实现。

template<typename T>
class List {
    template<typename U>
    struct Node {
        U data_;
        Node<U>* next_;

        Node() : data_(0), next_(nullptr) {}
        Node(U data) : data_(data), next_(nullptr) {}
    };

private:
    Node<T>* head_;
    std::size_t size_;

public:
    List() : head_{nullptr}, size_{0} {}

    void insert(const T& item) {
        Node<T>* p(new Node<T>(item));
        if (size_ == 0) {
            head_ = p;
        } else {
            p->next_ = head_;
            head_ = p;
        }
        size_++;
    }
    std::size_t getSize() {
        return size_;
    }

    ~List(){
    while(head_){
        Node<T> p = head_;
        delete(p);
        head_ = head_->next_;
    }
};

此代码似乎有效。尽管有 ~List() 析构函数，但问题是 new 分配的对象永远不会被清理。有人可以帮助我理解，我如何为这个 class 编写一个析构函数来清理所有分配的节点？[=14=]

重要说明：我知道这可以使用智能指针来完成，但我想了解管理堆的老派方法。

Answer 1

while(head_){
    Node<T> p = head_; <-- change to pointer
    delete(p); <-- you can't delete this right now
    head_ = head_->next_;
}

p 应该是一个指针。您无法立即删除 p。您必须找到 next 节点，然后删除 p。同样使用 delete p; 而不是 delete (p); 如下：

~List() {
    while(head_) {
        Node<T> *p = head_;
        head_ = head_->next_;
        delete p;
    }
}

如评论中所述，Node 不需要是模板。您可以简化您的 class。 insert也可以简化，因为head_被初始化为nullptr，可以放心地赋值p->next_ = head_;

template<typename T> class List {
    struct Node {
        T data_;
        Node* next_;
        Node() : data_(0), next_(nullptr) {}
        Node(T data) : data_(data), next_(nullptr) {}
    };
    Node* head_;
    std::size_t size_;
public:
    List() : head_{ nullptr }, size_{ 0 } {}

    void insert(const T& item) {
        Node* p = new Node(item);
        p->next_ = head_;
        head_ = p;
        size_++;
    }

    std::size_t getSize() {
        return size_;
    }

    ~List() {
        while(head_) {
            Node *marked = head_;
            head_ = head_->next_;
            delete marked;
        }
    }
};

Answer 2

一般的想法是，您必须弄清楚谁是对象的所有者，才能决定谁应该删除它。

相对于节点，列表是所有者。所以你应该仔细开发所有的方法，一旦列表失去对象的所有权，它确保对象被删除或所有权被接管。

当你想释放内存时，显而易见的地方是，第一个你删除列表。其次，当你删除一个元素时，例如弹出它。

让我们看看这两种情况。

首先删除列表。为此，您需要编写一个析构函数，它遍历列表并一个接一个地删除元素。为此，我参考了@barmak-shemiani 的回答。

对于弹出元素的情况，您可以执行以下操作：

  T pop() {
    Node<T> *tmp = head_;
    if (head_ != nullptr) {
      head_ = head_->next_;
      T data = tmp->data_;
      delete tmp;
      return data;
    }

    throw std::runtime_error("Can't pop an empty list")
  }

C++ 中列表 class 的析构函数

Destructor for a List class in C++

c++

containers

memory-management

object-lifetime

singly-linked-list