c++ - 一旦满足指定容量，覆盖优先级队列末尾的元素？

Question

我正在尝试在四叉树中搜索最近的 N 点，并使用 STL 优先级队列来存储找到的点（按与查询点的距离排序）。

超过查询点最大距离的点永远不会添加到队列中。但是，我也想切断搜索可以返回的项目数。目前，我添加了所有比最大距离更接近查询点的点，然后只从队列中读取前 N 个点。

在测试中，这太慢了——简单地添加比最大距离更近的每个点最终都会随着添加更多点而减慢。相反，我只想在队列中添加更多点：当前队列中的点少于 N 个，或者有问题的点比队列中的第 N 个点更靠近查询点，在这种情况下，该点被覆盖，并且不会增加队列中的元素数量。

有没有办法用 STL 优先级队列来做到这一点，还是我唯一的选择是自己写？

Answer 1

您在遍历它们时是否必须知道当前的 N 个最佳点？如果没有，也许您可​​以将所有点添加到随机访问容器（例如std::vector），然后std::partial_sort在最后调用以获得最佳 N。

如果您真的需要使用优先级队列来执行此操作，那是std::priority_queue不够的。您可以将一些东西与std::algorithm堆函数放在一起，这样您就可以访问底层容器。