Блог

Я хотел бы получить несколько советов о наилучших методах освобождения памяти для структур данных, используя BinomialHeap в качестве примера. Согласно разделу «Объединение» по этой ссылке, а также многим другим источникам,

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

метод union (куча x, куча 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) перед удалением куч, этот метод не должен существовать.

Я надеюсь, что ответ не «зависит от того, над чем вы работаете / кто использует класс / и т.д. и т.д.», Но что можно было бы считать «стандартной практикой» при решении проблем такого типа?

Прежде всего, я бы сказал, всегда используйте RAII для очистки ресурсов — предпочтительно с помощью std::unique_ptr , а не с помощью ручного delete вызова.

Судя по тому, как описана Union операция, я не думаю, что она должна фактически уничтожить объект в delete смысле, а скорее «деструктивно мутировать», крадя содержимое. Фактически именно так работает «семантика перемещения» C . После операции объект все еще существует, но у него нет ресурсов для очистки.

Чтобы описать, что я имею в виду, я буду использовать std::unique_ptr из C 11, который всегда переносит очистку ресурсов в RAII.

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

Heap Heap::Union(Heapamp;amp; left, Heapamp;amp; 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 .

Тогда использование этого кода было бы:

 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.