0

基本クラスHeapと 2 つの派生クラスMinHeapを使用して、MaxHeap以下に示します。

派生クラス オブジェクトを次のように作成します。

MinHeap* myminheap = new MinHeap();

しかし、それを使用して削除します

delete myminheap;

あり/なしでvirtual ~Heap() {}glibcメモリリークエラーが発生します! 核心は何ですか？私はこれに関する多くの投稿を通過しました.....

派生クラスでの new/delete 演算子のオーバーライド

派生クラス オブジェクトが削除されたときに基本クラス デストラクタ (仮想) が呼び出されるのはなぜですか?

基本クラス ポインターを使用して派生クラスを削除するとメモリ リークが発生する

....しかし、ベースデストラクタを仮想に設定してもメモリエラーが発生する理由を理解できませんか?

Heap* h_ptr = myminheap;
delete h_ptr;

ps。次のエラーがポップアップするため、派生クラス オブジェクト ポインターをベース ポインターに型キャストできません。

‘class Heap’ has no member named ‘insert’
‘class Heap’ has no member named ‘pop_min'

Heapクラスでそれらを紹介することで私が世話をすることができます

delete h_ptr;後で、呼び出す場合に呼び出す代わりfree(h_ptr);に、メモリリークの影響を受けないことに気付きました..万歳！しかし、私はこの振る舞いに光を当てる必要があります!

ヒープ.h

#include <cstdlib>
#include <vector>
#include <iterator>

using namespace std;

class Heap
{
  public:
    Heap() {}
    ~Heap() {}

    vector <int> heap;
    int left(int parent);
    int right(int parent);
    int parent(int child);
    int size()                  {return heap.size();}
    virtual void insert(int element) {}
    virtual int pop_min() {}
    virtual int pop_max() {}
    void print();
};

class MinHeap : public Heap
{
  private:
    void heapify_up(int index);
    void heapify_down(int index);

  public:
    MinHeap() {}
    ~MinHeap() {}

    int pop_min();
    void insert(int element);
};

class MaxHeap : public Heap
{
  private:
    void heapify_up(int index);
    void heapify_down(int index);

  public:
    MaxHeap() {}
    ~MaxHeap() {}

    int pop_max();
    void insert(int element);
};

heap.cc

#include <cstdlib>
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

#include "heap.h"

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int Heap::left(int parent)
{
    int i = (parent << 1) + 1;  //2 * parent + 1    read more on bit shifts
    return (i < heap.size()) ? i : -1;
}

int Heap::right(int parent)
{
    int i = (parent << 1) + 2;
    return (i < heap.size()) ? i : -1;
}

int Heap::parent(int child)
{
    if(child){
        int i = (child >> 1) - 1;
        return i;
    }
    else return -1;
}

void Heap::print()
{
    vector<int>::iterator i = heap.begin();
    cout << "Heap = ";
    while(i != heap.end()){
        cout << *i << " ";
        i++;
    }
    cout << endl;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int MinHeap::pop_min()
{
    int min = heap.front();
    heap[0] = heap[heap.size() - 1];
    heap.pop_back();
    heapify_down(0);
    return min;
}

void MinHeap::insert(int element)
{
    heap.push_back(element);
    heapify_up(heap.size() - 1);
}

void MinHeap::heapify_up(int index)
{
    while(index > 0 && parent(index) >= 0 && heap[parent(index)] > heap[index]){
        int temp = heap[index];
        heap[index] = heap[parent(index)];
        heap[parent(index)] = temp;
        index = parent(index);
    }
}

void MinHeap::heapify_down(int index)
{
    int child = left(index);

    if(child > 0 && right(index) > 0 && heap[child] > heap[right(index)])
        child = right(index);

    if(heap[index] > heap[child]){
        int temp = heap[child];
        heap[child] = heap[index];
        heap[index] = temp;
        heapify_down(child);
    }
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int MaxHeap::pop_max()
{
    int max = heap.front();
    heap[0] = heap[heap.size() - 1];
    heap.pop_back();
    heapify_down(0);
    return max;
}

void MaxHeap::insert(int element)
{
    heap.push_back(element);
    heapify_up(heap.size() - 1);
}

void MaxHeap::heapify_up(int index)
{
    while(index > 0 && parent(index) >= 0 && heap[parent(index)] < heap[index]){
        int temp = heap[index];
        heap[index] = heap[parent(index)];
        heap[parent(index)] = temp;
        index = parent(index);
    }
}

void MaxHeap::heapify_down(int index)
{
    int child = left(index);

    if(child > 0 && right(index) > 0 && child < right(index))
        child = right(index);

    if(heap[index] < heap[child]){
        int temp = heap[child];
        heap[child] = heap[index];
        heap[child] = temp;
        heapify_down(child);
    }
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//              test program
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int main(){
    // Create the heap
    MinHeap* myminheap = new MinHeap();
    myminheap->insert(700);
    myminheap->print();
    myminheap->insert(500);
    myminheap->print();
    myminheap->insert(100);
    myminheap->print();
    myminheap->insert(800);
    myminheap->print();
    myminheap->insert(200);
    myminheap->print();
    myminheap->insert(400);
    myminheap->print();
    myminheap->insert(900);
    myminheap->print();
    myminheap->insert(1000);
    myminheap->print();
    myminheap->insert(300);
    myminheap->print();
    myminheap->insert(600);
    myminheap->print();

    // Get priority element from the heap
    int heapSize = myminheap->size();
    for ( int i = 0; i < heapSize; i++ )
        cout << "Get min element = " << myminheap->pop_min() << endl;

    // Cleanup
    delete myminheap;

    return 1;
}
4

1 に答える 1

0

MinHeap を新規作成した場合、ヒープ タイプで free を呼び出して削除することはできません。あなたの問題は、オブジェクトへのポインターを保存していて、それが別のものだと言っていることです。その結果、削除ルーチンは、MinHeap を削除しようとしていることを認識せず、ヒープ部分のみを削除します (大まかに)。

myminheap オブジェクトで delete を直接呼び出すことができます。これは機能するはずです。

より良い解決策は、ヒープ上に MinHeap をまったく作成せず、スタック上に作成し、ポインターなしで使用することです。何らかの理由でヒープ上に作成する必要がある場合は、shared_ptr<> を使用するなど、代わりにスマート ポインター クラス内に作成すると、非常に役立ちます。

于 2013-04-10T09:17:13.053 に答える