Obtenir des éléments «std :: priority_queue» dans l'ordre inverse?

Question

J'ai écrit des méthodes de requête K-nearest-neighbor qui construisent une liste de points les plus proches d'un point de requête donné. Pour maintenir cette liste de voisins, j'utilise le std::priority_queue de sorte que l'élément supérieur est le voisin le plus éloigné du point de requête. De cette façon, je sais si je devrais pousser le nouvel élément qui est actuellement examiné (si à une distance moindre que le voisin le plus éloigné actuel) et peut apparaître () l'élément le plus éloigné lorsque ma fiabilité de priorité a plus que les éléments k.

Jusqu'à présent, tout va bien. Cependant, lorsque je publie les éléments, je voudrais les commander du plus proche du plus loin. Actuellement, je fais simplement éclater tous les éléments de la Priority-Quye et je les mets sur le contenant de la sortie (via un itérateur), ce qui se traduit par une séquence de points ordonnés du plus éloigné au plus proche, alors j'appelle alors, j'appelle alors que j'appelle alors std::reverse sur la plage d'itérateur de sortie.

À titre d'exemple simple, voici une recherche linéaire qui utilise la recherche prioritaire (évidemment, les méthodes de requête réelles de NEIGHBOR que j'utilise sont beaucoup plus compliquées):

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

Ce qui précède est tout dandy, sauf pour une chose: il nécessite que le type d'itulatrice de sortie soit bidirectionnel et pointe essentiellement vers un conteneur pré-alloué. Maintenant, cette pratique de stockage de la sortie dans une plage prescrite par un itérateur de sortie est également excellente et assez standard (par exemple std::copy et d'autres algorithmes STL en sont de bons exemples). Cependant, dans ce cas, je voudrais pouvoir ne nécessiter qu'un type de sortie de sortie avant, ce qui permettrait d'utiliser des itérateurs d'inserter en arrière comme ceux fournis pour les conteneurs STL et les iStreams.

Donc, cela se résume pour inverser la fibre de priorité avant de Vider son contenu dans l'itérateur de sortie. Donc, ce sont les meilleures options que j'ai pu trouver:

• Créer un std::vector, jetez le contenu prioritaire-yie et jetez les éléments dans l'itoratrice de sortie à l'aide d'un itérateur inversé sur le vecteur.

• Remplace le std::priority_queue avec un conteneur trié (par exemple std::multimap), puis vider le contenu dans l'itulatrice de sortie à l'aide de l'ordre de traversée approprié.

Y a-t-il une autre option raisonnable?

J'utilisais un std::multimap Dans une implémentation précédente de cet algorithme et d'autres, à partir de ma deuxième option ci-dessus. Cependant, quand je suis passé à std::priority_queue, le gain de performance était significatif. Donc, je préfère ne pas utiliser la deuxième option, car il semble vraiment que l'utilisation d'une fibre de priorité pour maintenir la liste des voisins est bien meilleure que de compter sur un tableau trié. Btw, j'ai aussi essayé un std::vector que je maintiens trié avec std::inplace_merge, ce qui était meilleur que le multimap, mais ne correspondait pas à la fibre de priorité.

En ce qui concerne la première option, qui est ma meilleure option à ce stade, il me semble juste du gaspillage de faire ce double transfert de données (file d'attente -> vecteur -> sortie). Je suis juste enclin à penser qu'il doit y avoir une façon plus simple de le faire ... quelque chose qui me manque.

La première option n'est vraiment pas si mauvaise dans cette application (compte tenu de la complexité de l'algorithme qui le précède), mais s'il y a une astuce pour éviter ce transfert de double mémoire, je voudrais le savoir.

Answer 1

Problème résolu!

Je suis tellement idiot ... Je savais que je manquais quelque chose d'évident. Dans ce cas, le std::sort_heap() fonction. La page de référence a même un exemple qui fait exactement ce dont j'ai besoin (et depuis le std::priority_queue est juste implémenté en termes de conteneur d'accès aléatoire et des fonctions de tas (pop_heap, push_heap, make_heap), il ne fait aucune différence réelle pour utiliser ces fonctions directement en place du std::priority_queue classer). Je ne sais pas comment j'aurais pu manquer ça.

Quoi qu'il en soit, j'espère que cela aide tous ceux qui ont eu le même problème.

Answer 2

Une idée sale, qui serait néanmoins garantie pour fonctionner, serait la suivante:

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

On peut noter que le tri en place brisera probablement la file d'attente.

Answer 3

Pourquoi ne spécifiez-vous pas simplement la fonction de comparaison opposée dans la déclaration:

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