Получение элементов std :: priority_queue в обратном порядке?

Я написал несколько методов запроса K-ближайшего соседа, которые создают список точек, ближайших к заданной точке запроса. Чтобы поддерживать этот список соседей, я использую std :: priority_queue , так что верхний элемент является самым дальним соседом для точки запроса. Таким образом, я знаю, следует ли мне протолкнуть новый элемент, который в настоящее время исследуется (если он находится на меньшем расстоянии, чем текущий самый дальний сосед), и могу ли я вытолкнуть () самый дальний элемент, когда моя очередь с приоритетом имеет более 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 , выгрузить в него содержимое очереди приоритетов и выгрузить элементы в выходной файл. итератор, использующий обратный итератор для вектора.

• Замените std :: priority_queue отсортированным контейнером (например, std :: multimap ), а затем выгрузите содержимое в итератор вывода, используя соответствующий порядок обхода.

Есть ли другой разумный вариант?

Я использовал std :: multimap в предыдущей реализации этого и других алгоритмов, как и в моем втором варианте выше. Однако, когда я переключился на std :: priority_queue , прирост производительности был значительным. Итак, я бы предпочел не использовать второй вариант, поскольку действительно кажется, что использование очереди приоритетов для поддержки списка соседей намного лучше, чем полагаться на отсортированный массив.Кстати, я также попробовал std :: vector , который я поддерживаю отсортированным с помощью std :: inplace_merge , который был лучше, чем multimap, но не соответствовал очереди приоритетов.

Что касается первого варианта, который на данный момент является моим лучшим вариантом, мне просто кажется расточительным выполнять эту двойную передачу данных (очередь -> вектор -> вывод). Я просто склонен думать, что должен быть более простой способ сделать это ... кое-что, чего мне не хватает ...

Первый вариант действительно не так уж плох в этом приложении (учитывая сложность алгоритма что предшествует этому), но если есть уловка, позволяющая избежать этой двойной передачи памяти, я хотел бы знать об этом.