在 BinomialHeap 实现中使用 delete in union(x, y)

Question

我想获得一些关于为数据结构释放内存的最佳实践的建议，以 BinomialHeap 为例。根据此 link 中的 'Union' 部分以及许多其他来源，

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap20.htm

方法 union(Heap x, Heap y) 将销毁 x 和 y，但不会销毁它们指向的列表。

但是，从逻辑的角度来看，我想知道如何最好地在 C++ 中实现它。我知道我可以像这样写一个析构函数..

class BinomialHeap{
public:
    Node* head;
    int size;
    ~BinomialHeap() { head = nullptr; };
  // other methods
};

然后在 Union(x, y) 中删除它，以释放内存，就像这样...

Heap* BinomialHeap::Union(Heap* x, Heap* y) {     // assume x and y, and all their nodes, were dynamically allocated
   Node* x_head = x->head;
   Node* y_head = y->head;
   delete x;
   delete y;
   // code to merge x_head with y_head
};

... 会使 x 本身的头节点保持不变。尽管如此，我想知道它是否是智能设计写一个析构函数，它（在我看来）应该在概念上以这种方式释放与对象关联的所有内存。如果没有，是不是写一个像下面这样的方法会更好？

class BinomialHeap{
private:
    void union_delete();
   // other code
};

void BinomialHeap::union_delete() {
    head = nullptr;
    delete this;
};

我理解调用 delete this 的问题，但由于我在“现实世界”中使用 BinomialHeap 的经验有限，我无法想象黑客之外的情况，只要我对head_nodes (head_x, head_y) 在删除堆之前，这个方法不应该存在。

我希望答案不是“取决于你在做什么 on/who 使用 class/etc 等”，而是在交易中人们会认为什么是“标准做法”遇到此类问题？

Answer 1

首先，我想说总是使用 RAII 进行资源清理——最好通过 std::unique_ptr 而不是使用手动 delete 调用。

从描述 Union 操作的方式来看，我不认为它必须 实际上 销毁 delete 意义上的对象，但是而是通过窃取内容来“破坏性变异”。这实际上是 C++ 的“move-semantics”的工作方式。运行后对象依然存在，只是没有资源需要清理

为了描述我的意思，我将使用 C++11 中的 std::unique_ptr，它始终在 RAII 中包装资源清理。

class Heap
{
public:
    // Move two heaps to create a 'Union' of two heaps
    static Heap Union(Heap&& lhs, Heap&& rhs);
    // ...
private:
    // unique_ptr ensures it gets deleted when destructed
    std::unique_ptr<Node> m_head;
};

Heap Heap::Union(Heap&& left, Heap&& right)
{
    // destructively mutate 'left' and 'right'; but we don't have to "destroy" 'left' and 'right'
    auto l = std::move(lhs.m_head);
    auto r = std::move(rhs.m_head):

    // create the new 'Heap' from the above and return it
};

在这种情况下，我们实际上并不是在“破坏”该对象，而是将其取出并任其自生自灭。这实际上也是 C++ 中“move-semantics”背后的相同概念。

此代码的用途是：

auto a = /* Heap A */
auto b = /* Heap B */
auto c = Heap::Union( std::move(a), std::move(b) );

// 'a' and 'b' still exist (aren't destroyed) but no longer contain any data.

在 BinomialHeap 实现中使用 delete in union(x, y)

Use of delete in union(x, y) in a BinomialHeap implementation

c++

memory

heap