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

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

到目前为止,一切都很好.但是,当我输出元素时,我想从最接近最远的位置订购它们.目前,我只是从优先级队列中弹出所有元素并将它们放在输出容器上(通过迭代器),这会导致从最远到最近排序的点序列,因此,我调用std :: reverse on输出迭代器范围.

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

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,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,在其中转储优先级队列内容,并使用向量上的反向迭代器将元素转储到output-iterator中.
>将std :: priority_queue替换为已排序的容器(例如std :: multimap),然后使用适当的遍历顺序将内容转储到output-iterator中.

还有其他合理的选择吗？

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

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

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