以相反的顺序获取`std :: priority_queue`元素？

Question

我写了一些K-nearest-neighbor查询方法,它们构建了一个最接近给定查询点的点列表.为了维护该邻居列表,我使用std::priority_queue了top元素是查询点的最远邻居.这样我知道是否应该推送当前正在检查的新元素(如果距离当前最远的邻居的距离较小),并且当我的优先级队列具有多于K个元素时,可以弹出()最远的元素.

到目前为止,一切都很好.但是,当我输出元素时,我想从最接近最远的位置订购它们.目前,我只是从优先级队列中弹出所有元素并将它们放在输出容器上(通过迭代器),这会导致从最远到最近排序的一系列点,因此,我调用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容器和iostreams那样的后插件迭代器.

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

• 创建一个std::vector,在其中转储优先级队列内容,并使用向量上的反向迭代器将元素转储到输出迭代器中.

• 将sort替换为std::priority_queue已排序的容器(例如std::multimap),然后使用适当的遍历顺序将内容转储到output-iterator中.

还有其他合理的选择吗？

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

至于第一个选项,这是我此时的最佳选择,我不得不进行双重数据传输(queue - > vector - > output).我只是倾向于认为必须有一种更简单的方法来做这件事......我缺少的东西......

第一个选项在这个应用程序中确实并不坏(考虑到它之前的算法的复杂性),但如果有一个技巧可以避免这种双内存传输,我想知道它.

Answer 1

问题解决了!

我是个白痴......我知道我错过了一些明显的东西.在这种情况下,std::sort_heap()功能.该参考页甚至有不正是我所需要的(并且因为一个例子std::priority_queue只是在随机访问容器和堆函数方面实现(pop_heap,push_heap,make_heap)它并没有真正的区别,直接使用这些功能取而代之的std::priority_queue).我不知道怎么会错过那个.

无论如何,我希望这可以帮助任何有同样问题的人.