我已经编写了一些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），然后使用适当的遍历顺序将内容转储到输出迭代器中。
还有其他合理的选择吗？
从上面的第二个选项开始，我曾在该算法和其他算法的先前实现中使用std::multimap。然而，当我切换到std::priority_queue时，性能提升是显著的。因此，我宁愿不使用第二个选项，因为使用优先级队列来维护邻居列表似乎比依赖排序数组要好得多。顺便说一句，我还尝试了一个std::vector，我用std::inplace_merge进行排序，它比多映射更好，但与优先级队列不匹配。
至于第一个选项，这是我目前最好的选项，对我来说，必须进行这种双重数据传输（队列->向量->输出）似乎很浪费。我只是倾向于认为必须有一种更简单的方法来做到这一点。。。我缺少的东西。。
第一个选项在这个应用程序中确实没有那么糟糕（考虑到之前算法的复杂性），但如果有什么技巧可以避免这种双重内存转移，我想知道它。
问题解决了！
我真是个白痴。。。我知道我错过了一些显而易见的东西。在这种情况下，std::sort_heap()函数。参考页面甚至有一个例子正好满足了我的需求（由于std::priority_queue只是根据随机访问容器和堆函数（pop_heap、push_heap和make_heap）来实现的，因此直接使用这些函数代替std::priority_queue类并没有什么真正的区别）。我不知道我怎么会错过。
无论如何，我希望这能帮助到任何有同样问题的人。
一个肮脏的想法是：
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;
}
需要注意的是，就地排序可能会破坏队列。
为什么不在声明中指定相反的比较函数：
#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;
}