Ottenere gli elementi `std :: priority_queue` in ordine inverso?

Question

Ho scritto alcuni metodi di query K-closest-vicini che creano un elenco di punti più vicini a un determinato punto di query. Per mantenere quella lista di vicini, utilizzo lo std::priority_queue in modo tale che l'elemento in alto sia il vicino più lontano dal punto di interrogazione. In questo modo so se dovrei spingere il nuovo elemento che viene attualmente esaminato (se ad una distanza minore rispetto al vicino più lontano corrente) e pop() l'elemento più lontano quando la mia coda di priorità ha più di elementi K.

Finora, tutto va bene. Tuttavia, quando emetto gli elementi, vorrei ordinarli dal più vicino al più lontano. Attualmente, inserisco semplicemente tutti gli elementi dalla coda di priorità e li metto nel contenitore di output (attraverso un iteratore), il che si traduce in una sequenza di punti ordinati dal più lontano al più vicino, quindi, io chiamo std::reverse sull'outer di output gamma.

Come semplice esempio, ecco un lineare di ricerca che utilizza la coda con priorità (ovviamente, l'attuale metodi di query primi vicini che uso sono molto più complicato):

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

È possibile che questo è tutto dandy ad eccezione di una cosa: richiede che il tipo di output-iterator sia bidirezionale e punta essenzialmente a un contenitore pre-allocato. Ora, questa pratica di immagazzinare l'uscita in un intervallo prescritto da un certo iteratore di uscita è ottima e abbastanza standard (ad esempio, std::copy e altri algoritmi STL ne sono un buon esempio). Tuttavia, in questo caso mi piacerebbe essere in grado di richiedere solo un tipo di iteratore di output in avanti, che renderebbe possibile l'uso di iteratori di back-inserter come quelli forniti per contenitori STL e iostreams.

Quindi, questo si riduce a invertire la coda con priorità prima di dumping suo contenuto nel iteratore di uscita. Quindi, queste sono le opzioni migliori sono stato in grado di venire con:

• Creare un std::vector, il dump del contenuto di coda con priorità in essa, e scaricare gli elementi in uscita-iteratore utilizzando un inversa iteratore sul vettore.

• Sostituire std::priority_queue con un contenitore ordinato (ad esempio std::multimap), quindi eseguire il dump del contenuto nell'outer-output utilizzando l'ordine di attraversamento appropriato.

C'è qualche altra opzione ragionevole?

Ho utilizzato uno std::multimap in un'implementazione precedente di questo algoritmo e altri, a partire dalla seconda opzione sopra riportata. Tuttavia, quando sono passato a std::priority_queue, il guadagno di prestazioni è stato significativo. Quindi, preferirei non usare la seconda opzione, poiché sembra davvero che usare una coda di priorità per mantenere l'elenco dei vicini sia molto meglio che fare affidamento su una matrice ordinata. A proposito, ho anche provato un std::vector che mantengo ordinato con std::inplace_merge, che era meglio di multimap, ma non corrispondeva alla coda di priorità.

Per quanto riguarda la prima opzione, che è la mia migliore opzione a questo punto, mi sembra semplicemente inutile dover fare questo doppio trasferimento di dati (coda -> vettore -> output). Sono solo incline a pensare che ci sia un modo più semplice per farlo ... qualcosa che mi manca ..

La prima opzione non è poi così male in questa applicazione (considerando la complessità del algoritmo che lo precede), ma se c'è un trucco per evitare questo doppio trasferimento di memoria, mi piacerebbe saperlo.

Answer 1

Problema risolto!

Sono un tale idiota ... Sapevo che mi mancava qualcosa di ovvio. In questo caso, la funzione std::sort_heap(). Lo reference page ha anche un esempio che fa esattamente ciò di cui ho bisogno (e dato che lo std::priority_queue è appena implementato in termini di contenitore ad accesso casuale e funzioni heap (pop_heap, push_heap, make_heap) non fa alcuna differenza per usare direttamente queste funzioni sul posto della classe std::priority_queue). Non so come avrei potuto essermi perso.

In ogni caso, spero che questo aiuti chiunque abbia avuto lo stesso problema.

Answer 2

Un'idea sporca, che sarebbe comunque essere garantito il funzionamento, sarebbe il seguente:

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

Si può osservare che l'ordinamento sul posto sarà probabilmente rompere la coda.

Answer 3

Perché non basta specificare la funzione di confronto opposta nella dichiarazione:

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