1

所以这是一个概念性的问题。我正在用 C++ 编写 LinkedList，因为 Java 是我的第一语言，所以我开始编写我的 removeAll 函数，以便它只连接头部和尾部节点（顺便说一句，我正在使用哨兵节点）。但我立即意识到这在 C++ 中不起作用，因为我必须为节点释放内存！

有没有办法遍历整个列表，手动删除每个元素？

4

3 回答 3

7

你可以让每个节点拥有下一个，即当它自己被销毁时负责销毁它。您可以使用以下智能指针来执行此操作std::unique_ptr：

struct node {
    // blah blah
    std::unique_ptr<node> next;
};

然后你可以只销毁第一个节点，所有其他节点都将被计算在内：它们都将在 unique_ptr 析构函数的连锁反应中被销毁。

但是，如果这是一个双向链表，则不应unique_ptr在两个方向上都使用 s。这将使每个节点拥有下一个节点，并由下一个节点拥有！您应该使这种所有权关系仅存在于一个方向。在另一个使用常规的非拥有指针：node* previous;

但是，这对哨兵节点不起作用：它不应该被销毁。如何处理取决于如何识别哨兵节点以及列表的其他属性。

如果您可以轻松区分哨兵节点，例如检查布尔成员，则可以使用自定义删除器来避免删除哨兵：

struct delete_if_not_sentinel {
    void operator()(node* ptr) const {
        if(!ptr->is_sentinel) delete ptr;
    }
};

typedef std::unique_ptr<node, delete_if_not_sentinel> node_handle;

struct node {
    // blah blah
    node_handle next;
};

这停止了​​哨兵的连锁反应。

于 2012-08-23T02:15:29.747 回答
1

如果您使用 c++垃圾收集器，您可以像 Java 一样进行操作。没有多少人这样做。无论如何，它最多可以为您节省运行时间的一个常数因素，因为无论如何您都要花费成本来分配列表中的每个元素。

于 2012-08-23T02:04:33.807 回答
0

是的。好吧，有点...如果您实现列表以使用内存池，那么它负责该池中的所有数据，并且可以通过删除内存池（可能包含一个或多个大块内存）来删除整个列表）。

使用内存池时，通常至少有以下考虑之一：

  • 对象创建和销毁方式的限制；
  • 您可以存储何种数据的限制；
  • 每个节点的额外内存需求（引用池）；
  • 一个简单、直观的池与一个复杂、令人困惑的池。

我不是这方面的专家。通常，当我需要快速内存管理时，它是用于填充一次的内存，无需维护空闲列表等。当您有特定的目标和设计约束时，内存池更容易设计和实现。如果你想要一些适用于所有情况的灵丹妙药，那你可能就不走运了。

于 2012-08-23T02:14:35.270 回答