6

我已经编写了一些 K-nearest-neighbor 查询方法，这些方法构建了一个最接近给定查询点的点列表。为了维护该邻居列表，我使用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，转储其中的优先级队列内容，并使用向量上的反向迭代器将元素转储到输出迭代器中。

  • 将 替换为std::priority_queue已排序的容器（例如std::multimap），然后使用适当的遍历顺序将内容转储到输出迭代器中。

还有其他合理的选择吗？

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

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

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

4

3 回答 3

5

问题解决了！

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

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

于 2012-02-25T02:38:29.190 回答
3

一个肮脏的想法，但可以保证有效，如下：

std::priority_queue<int, std::vector<int>, std::less<int> > queue;
queue.push(3);
queue.push(5);
queue.push(9);
queue.push(2);

// Prints in reverse order.
int* front = const_cast<int*>(&queue.top());
int* back = const_cast<int*>(front + queue.size());
std::sort(front, back);
while (front < back) {
    printf("%i ", *front);
    ++front;
}

可以注意到，就地排序可能会破坏队列。

于 2012-02-24T22:44:45.647 回答
3

为什么不在声明中指定相反的比较函数：

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int> > pq;
    pq.push(1);
    pq.push(10);
    pq.push(15);
    std::cout << pq.top() << std::endl;
}
于 2012-09-25T13:48:20.970 回答