提取 priority_queue 的最后一个元素

Question

我正在使用 std::priority_queue 编写一个算法来计算 3D 网格上数据集的距离函数。初始化队列后，我想将最后一个元素存储在一个单独的变量中，就像您使用 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。因此，为了在访问第 3 环邻域后停止此过程，我必须跟踪当前环的最后一个元素。

Answer 1

"obvious" 方法是将最后一个（最小）元素的副本与 priority_queue 一起存储。跟踪这个的额外工作与添加到优先级队列的元素数量成正比，而你的解决方法是在你调用它时队列大小的 N log(N)，所以你自己选择。

每当您 pop 时，根据定义，如果 pop 导致队列为空，您只能删除最后一个值，因此您无需担心更新 pop.

每当您 push 到优先级队列时，将被推送的值与当前最小值进行比较，并在必要时替换它。 emplace.

也是如此

如果你真的很喜欢，你可以通过编写你自己的容器适配器来展示它，priority_queue_that_additionally_accesses_the_min_value。或者更短的名字。

如果您需要访问实际元素，而不是它的副本，那么您会遇到一个问题，因为 priority_queue 本身会在您不看的时候在内部四处移动，因此您可以'只是保持指针指向最小值。将元素包装在智能指针中可能会解决这个问题，当然你需要提供 priority_queue 一个比较器来引用智能指针。

终于有个"double-ended priority queue"了。这将使您能够有效地去除两端，而不是有效地从一端去除并检查两端。它不在标准 C++ 中，但要么查找必要的结构和算法并自己实现，要么搜索 "double-ended priority queue" 或 "min/max heap" 的 C++ 实现。我自己从来没有使用过这个结构，所以我不会推荐一个特定的结构。

提取 priority_queue 的最后一个元素

Extracting last element of a priority_queue

c++

queue

priority-queue