Obteniendo los elementos `std :: priority_queue` en orden inverso?

Question

He escrito algunos métodos de consulta K-vecino más cercano que crean una lista de puntos que están más cerca de un punto de consulta determinado. Para mantener esa lista de vecinos, utilizo el std::priority_queue de modo que el elemento superior sea el vecino más alejado del punto de consulta. De esta forma sé si debo presionar el nuevo elemento que se está examinando actualmente (si está a una distancia menor que el vecino más alejado actual) y puedo hacer estallar() el elemento más lejano cuando mi prioridad-cola tiene más de K elementos.

Hasta ahora, todo está bien. Sin embargo, cuando publico los elementos, me gustaría ordenarlos desde el más cercano al más lejano. Actualmente, simplemente aparezco todos los elementos de la cola de prioridad y los pongo en el contenedor de salida (a través de un iterador), lo que da como resultado una secuencia de puntos ordenados desde el más lejano al más cercano, entonces llamo al std::reverse en el iterador de salida distancia.

Como un simple ejemplo, aquí es una búsqueda lineal que utiliza la prioridad en colas (obviamente, los métodos de consulta del vecino más cercano reales que uso son mucho más complicadas):

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; 
    }; 

Lo anterior es todo Dandy, excepto por una cosa: requiere que el tipo de iterador de salida sea bidireccional y que esencialmente apunte a un contenedor preasignado. Ahora, esta práctica de almacenar la salida en un rango prescrito por algún iterador de salida es excelente y bastante estándar también (por ejemplo, std::copy y otros algoritmos de STL son buenos ejemplos de eso). Sin embargo, en este caso, me gustaría poder solicitar solo un tipo de iterador de salida hacia adelante, lo que permitiría utilizar iteradores de inserción inversa como los provistos para contenedores STL y iostreams.

Por lo tanto, esto se reduce a revertir la cola de prioridad antes de volcar su contenido en el iterador de salida. Por lo tanto, éstas son las mejores opciones que he podido llegar a:

• Crear un std::vector, volcar el contenido de prioridades de colas en ella, y volcar los elementos en la salida-iterador utilizando una inversa iterador en el vector.

• Reemplace el std::priority_queue con un contenedor clasificado (por ejemplo, std::multimap), y luego volcar el contenido en el iterador de salida utilizando el orden transversal adecuado.

¿Hay alguna otra opción razonable?

Solía ​​emplear un std::multimap en una implementación previa de este algoritmo y otros, a partir de mi segunda opción anterior. Sin embargo, cuando cambié al std::priority_queue, la ganancia de rendimiento fue significativa. Por lo tanto, prefiero no utilizar la segunda opción, ya que parece que utilizar una cola de prioridad para mantener la lista de vecinos es mucho mejor que confiar en una matriz ordenada. Por cierto, también probé un std::vector que mantengo ordenado con std::inplace_merge, que era mejor que multimap, pero no coincidía con la cola de prioridad.

En cuanto a la primera opción, que es mi mejor opción en este momento, me parece un desperdicio tener que hacer esta doble transferencia de datos (cola -> vector -> salida). Me inclino a pensar que debe haber una manera más simple de hacer esto ... algo que me falta ...

La primera opción realmente no es tan mala en esta aplicación (considerando la complejidad del algoritmo que lo precede), pero si hay un truco para evitar esta doble transferencia de memoria, me gustaría saberlo.

Answer 1

¡Problema resuelto!

Soy un idiota ... Sabía que me estaba perdiendo algo obvio. En este caso, la función std::sort_heap(). El reference page incluso tiene un ejemplo que hace exactamente lo que necesito (y dado que el std::priority_queue acaba de implementarse en términos de un contenedor de acceso aleatorio y las funciones de montón (pop_heap, push_heap, make_heap) no hace ninguna diferencia usar estas funciones directamente en el lugar de la clase std::priority_queue). No sé cómo podría haberme perdido eso.

De todos modos, espero que esto ayude a cualquiera que tenga el mismo problema.

Answer 2

Una idea sucia, que sin embargo se garantiza que funcione, sería la siguiente:

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; 
} 

Puede observarse que la clasificación en el lugar donde es probable que romper la cola.

Answer 3

¿Por qué no basta con especificar la función de comparación opuesta en la declaración:

#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; 
}