C++雙向關聯內存管理策略

Question

我使用兩個名爲IndexedHeap和HeapEntry的類實現了一個堆。我有一些損壞的內存訪問導致segfaults，我相信我知道在哪裏/爲什麼，但我不知道如何解決它。以下是我迄今爲止設計類的方法：

class IndexedHeap 
{ 
private: 
    std::vector<HeapEntry*> heap; // the entries held by this heap 
public: 
    ... 
}; 

class HeapEntry 
{ 
private: 
    int index; 
    size_t priority; 
    unsigned long long key; 
    IndexedHeap* myHeap; // reference to heap where this entry resides 
public: 
    HeapEntry(unsigned long long key, size_t priority, IndexedHeap* myHeap) 
     : key(key), priority(priority), index(-1), myHeap(myHeap) 
    {} 
}; 

堆和它的條目都需要相互引用。正如你所看到的，我決定使用一個原始指針指向HeapEntry中的IndexedHeap。這是我認爲我出錯的地方，但我不確定。

在整個程序執行過程中，都會創建新的堆條目，作爲一堆的一部分。條目也從這堆中刪除並銷燬。也許當一個堆條目被銷燬時，它指向的堆被損壞。這將解釋我的內存問題，因爲下次堆入口嘗試訪問堆時，它將訪問已釋放的內存。

不幸的是，我並不相信這一點。我沒有實現HeapEntry的析構函數。默認的析構函數只是調用一個類的所有實例變量的析構函數？那麼指向myHeap的指針會不會被破壞，而堆對象本身還能存活？

那麼，設計這種關係的正確方法是什麼？我的記憶問題可以從我發佈的代碼中解釋出來嗎？謝謝，請讓我知道你是否想看更多的代碼或更多的細節。

HeapEntry* IndexedHeap::insert(unsigned long long key) 
{ 
    HeapEntry* entry = new HeapEntry(key, 1, this); 
    heap.push_back(entry); 
    int index = heapifyUp(heap.size() - 1); 
    heap[index]->setIndex(index); 
    return entry; 
} 

void IndexedHeap::deleteAtIndex(int pos) 
{ 
    if (pos >= 0 && pos < heap.size()) 
    { 
     // Copy heap.back() into the position of target, thus overwriting it 
     *heap[pos] = *heap.back(); 

     // Fix the index field for the just copied element 
     heap[pos]->setIndex(pos); 

     // We've removed the target by overwriting it with heap.back() 
     // Now get rid the extra copy of heap.back() 
     // Release the mem, then pop back to get rid of the pointer 
     delete heap.back(); 
     heap.pop_back(); 

     // Heapify from the position we just messed with 
     // use heapifyDown because back() always has a lower priority than the element we are removing 
     heapifyDown(pos); 
    } 
} 

Answer 1

嗯，首先，你使用STL從優先級隊列，或者使用多重映射爲優先級隊列的arent原因：創建並在堆破壞項

碼？它比編寫自己的解決方案更好。

接下來，代碼結構：std::vector<HeapEntry*> heap;因內存泄漏而臭名昭着，人們沒有刪除指向的內存，而當人們嘗試刪除指向的內存並導致刪除錯誤時導致嚴重的內存故障。

"IndexedHeap* myHeap;"很可能不是你的問題。如果有人刪除了這些對象，那麼對您不擁有的事物的引用可能會成爲問題，但是到那時您可能會停止使用這些對象。順便說一句，既然它是一個引用，你應該考慮把它作爲一個引用（然後在ctr期間綁定並且永遠不會改變） - 但是這會改變代碼的安全性。如你所知，指針的dtr對目標沒有任何影響。

你可以運行valgrind嗎？它很快解決了這樣的問題。否則：

請嘗試不刪除任何條目，並查看是否能夠阻止您的錯誤，如果是的話。

您還可以嘗試跟蹤您新建和刪除的指針，可以通過打印或通過全局設置/地圖對象進行跟蹤。這可以方便地找到這些東西。