自定义类指针优先级队列上的声明错误

我正在实现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

自定义类指针优先级队列上的声明错误

回答

相关问题