我使用一个std::priority_queue来编写一个算法来计算三维网格上数据集的距离函数。初始化队列后,我想将最后一个元素存储在一个单独的变量中,就像使用std::queue.back()一样,但是当然,优先级队列是不可能的,所以我的工作如下:
CellQueue q; //this is the actual priority_queue
//...
//initialization
//...
Cell* last = 0;
CellQueue dummy(q);
while (!dummy.empty()) {
last = dummy.top();
dummy.pop();
}当然有更好的方法来解决这个问题,所以如果有人能给我看的话,我会很高兴的。
谢谢,
费德里科
编辑
@Sam @Dietmar计算距离函数(DF)的算法是这样工作的:在priority_queue中填充至少包含数据集一个点的网格单元格,然后按距离(这一步为零)按递增顺序排序。然后,对于队列的每个元素,访问邻居,并为每个邻居计算相对于其父元素的距离。现在,出于效率原因,我只想在数据集周围的一个窄带上计算DF。因此,为了停止这个过程后,访问了第三环邻里,我必须跟踪当前环的最后一个元素。
发布于 2016-05-31 10:38:33
“显而易见”的方法是与priority_queue一起存储最后一个(最小)元素的副本。跟踪这一点的额外工作与添加到优先级队列中的元素数量成正比,而您的解决方法是调用队列时队列大小的N个log(N),所以请选择。
无论何时pop,根据定义,只有当pop导致队列为空时,才能删除最后一个值,因此不需要担心更新pop上的任何内容。
每当您push到优先级队列时,将正在推送的值与当前的最小值进行比较,并在必要时替换它。emplace也是如此。
如果您想成为真正的花花公子,您可以通过编写您自己的容器适配器priority_queue_that_additionally_accesses_the_min_value来展示这一点。或者更短的名字。
如果您需要访问实际的元素,而不是它的副本,那么您就会遇到一个问题,即priority_queue本身将在您不查看的情况下在内部移动,因此不能只将指针保持在最小值。将元素封装在智能指针中可能会处理这个问题,当然,您需要为priority_queue提供一个比较器来判断智能指针。
最后,出现了“双结束优先级队列”.这将允许您有效地移除两端,而不是有效地从一端移除和检查两者。它不是在标准C++中,而是查找必要的结构和算法并自己实现,或者搜索“双端优先级队列”或"min/max堆“的C++实现。我自己从来没有使用过这种结构,所以我不会推荐具体的结构。
https://stackoverflow.com/questions/37542974
复制相似问题