小编Mik*_*son的帖子

我写了一些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() …