自定義類指針優先級隊列上的聲明錯誤

我正在實現A *搜索算法，但我一直遇到優先級隊列的問題。自定義類指針優先級隊列上的聲明錯誤

class CNode; 

struct CompareNode : public binary_function<CNode*, CNode*, bool> { 
    bool operator()(const CNode* lhs, const CNode* rhs) const { 
     return lhs->m_costFromStart+lhs->m_heuristic > rhs->m_costFromStart+rhs->m_heuristic; 
    } 
}; 


bool AStarSearch(CNode* start, CNode* end) { 
    priority_queue<CNode*, vector<CNode*>, CompareNode> open; 
    ... 
}

調用堆棧：

std::_Debug_heap ... 
std::pop_heap ... 
std::priority_queue<CNode *,std::vector<CNode *,std::allocator<CNode *> >,CompareNode>::pop() 
AStarSearch(CNode * start=0x0f9a23b8, CNode * end=0x0f9a24e8)

大於作爲我需要最小堆被用來我已經根據this article

這是相關的代碼中實施的優先級隊列中的自定義比較器對於這個算法。實現似乎工作正常，並且問題在發佈模式下運行時消失，但優先級隊列在pop（）ed時，在調試模式下偶爾會拋出「Invalid heap」斷言失敗。

我不熟悉stl中的binary_function，但問題似乎在於比較器。刪除比較器或將符號更改爲更少，然後刪除錯誤，但這會給我一個最大的堆。有什麼我失蹤？

來源

2011-09-17 Skul

「斷言錯誤」 - 請指定更多，錯誤在哪裏以及調用堆棧是什麼 –

您損壞了堆。發生這種情況時，您看到錯誤的地方可能會告訴您很少有關錯誤的根源。嘗試着寫下所有的內存寫入，並可能添加自己的斷言。如果你沒有很多代碼，你可以在這裏發佈。否則，幾乎不可能猜出錯誤的根源。此外，請注意，堆損壞對更改很敏感 - 更改爲最大堆可能無法解決問題，但它會爲您隱藏當前代碼。嘗試解決問題而不作進一步修改 - 能夠重現問題是解決問題的一個途徑。 – eran

需要注意的一個重要細節是，在A *（或Dijkstra's）中，最終會改變已經在堆中的元素的優先級。 'std :: priority_queue'類不適用於此;如果更改元素的優先級，則優先級隊列不會自動更新以修復它;你必須自己做這個。這可能會解釋你所看到的行爲。 – templatetypedef

感謝您的幫助。事實證明，在改變優先級隊列中的節點成本之後，我沒有重建堆。調用

make_heap(const_cast<CNode**>(&open.top()), const_cast<CNode**>(&open.top()) + open.size(), 
CompareNode());

每次修改pq後都解決了這個問題。

來源

2011-09-18 04:39:43 Skul

自定義類指針優先級隊列上的聲明錯誤

回答

相關問題