c++ - 逆序获取 `std::priority_queue`个元素？

Question

我编写了一些 K 最近邻查询方法，这些方法构建了一个最接近给定查询点的点列表。为维护该邻居列表，我使用 std::priority_queue 使得顶部元素是距查询点最远的邻居。这样我就知道我是否应该推送当前正在检查的新元素(如果距离比当前最远的邻居更小)并且当我的优先级队列有超过 K 个元素时可以 pop() 最远的元素。

到目前为止，一切都很好。但是，当我输出元素时，我想从最近到最远的顺序排列它们。目前，我只是简单地从优先级队列中弹出所有元素并将它们放在输出容器中(通过迭代器)，这会产生从最远到最近排序的点序列，然后，我调用 std: :reverse 在输出迭代器范围上。

作为一个简单的例子，这是一个使用优先级队列的线性搜索(显然，我使用的实际最近邻查询方法要复杂得多):

  template <typename DistanceValue,
            typename ForwardIterator,
            typename OutputIterator,
            typename GetDistanceFunction,
            typename CompareFunction>
  inline 
  OutputIterator min_dist_linear_search(ForwardIterator first,
                                        ForwardIterator last,
                                        OutputIterator output_first,
                                        GetDistanceFunction distance,
                                        CompareFunction compare,
                                        std::size_t max_neighbors = 1,
                                        DistanceValue radius = std::numeric_limits<DistanceValue>::infinity()) {
    if(first == last) 
      return output_first;

    typedef std::priority_queue< std::pair<DistanceValue, ForwardIterator>, 
                                 std::vector< std::pair<DistanceValue, ForwardIterator> >,
                                 detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction> > PriorityQueue; 

    PriorityQueue output_queue = PriorityQueue(detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction>(compare));

    for(; first != last; ++first) {
      DistanceValue d = distance(*first);
      if(!compare(d, radius)) 
        continue;

      output_queue.push(std::pair<DistanceValue, ForwardIterator>(d, first));

      while(output_queue.size() > max_neighbors)
        output_queue.pop();

      if(output_queue.size() == max_neighbors)
        radius = output_queue.top().first;
    };

    OutputIterator it = output_first;
    while( !output_queue.empty() ) {
      *it = *(output_queue.top().second);
      output_queue.pop(); ++it;
    };
    std::reverse(output_first, it);
    return it;
  };

除了一件事之外，以上都是花花公子:它要求输出迭代器类型是双向的，并且基本上指向一个预先分配的容器。现在，这种将输出存储在某个输出迭代器规定的范围内的做法非常好，也非常标准(例如 std::copy 和其他 STL 算法就是很好的例子)。但是，在这种情况下，我希望能够只需要一个前向输出迭代器类型，这样就可以使用为 STL 容器和 iostream 提供的后向插入器迭代器。

因此，这归结为在将其内容转储到输出迭代器中之前反转优先级队列。所以，这些是我能够想出的更好的选择:

• 创建一个 std::vector，将优先级队列内容转储到其中，然后使用 vector 上的反向迭代器将元素转储到输出迭代器中。

• 将 std::priority_queue 替换为已排序的容器(例如 std::multimap)，然后使用适当的遍历顺序。

还有其他合理的选择吗？

我以前在这个算法和其他算法的实现中使用了 std::multimap，作为我上面的第二个选项。但是，当我切换到 std::priority_queue 时，性能提升非常显着。所以，我宁愿不使用第二个选项，因为看起来使用优先级队列来维护邻居列表比依赖排序数组要好得多。顺便说一句，我还尝试了一个 std::vector，我用 std::inplace_merge 维护排序，这比 multimap 好，但与优先级不匹配 -排队。

至于第一个选项，这是我目前最好的选择，对我来说，必须进行这种双重数据传输(队列 -> vector -> 输出)似乎很浪费。我只是倾向于认为必须有一种更简单的方法来做到这一点……我缺少的东西……

第一个选项在这个应用程序中确实没有那么糟糕(考虑到它之前的算法的复杂性)，但如果有避免这种双重内存传输的技巧，我想知道它。

Answer 1

问题解决了!

我真是个白痴……我知道我错过了一些明显的东西。在这种情况下，std::sort_heap() 函数。 reference page甚至有一个完全符合我需要的示例(因为 std::priority_queue 只是根据随机访问容器和堆函数(pop_heap、push_heap、make_heap)实现的)直接代替 std::priority_queue 类使用这些函数没有真正的区别)。我不知道我怎么会错过。

无论如何，我希望这对遇到同样问题的人有所帮助。