Comment itérer sur une file d'attente de priorité?

puis-je parcourir un standard priority_queue ou un standard queue en c++ avec un itérateur (comme un vector )? Je ne veux pas utiliser pop parce que ça cause ma file d'attente d'être démontée.

Merci pour toute aide

46
demandé sur Björn Pollex 2010-12-19 22:50:36

13 réponses

A queue fournit intentionnellement une interface limitée, ce qui exclut l'itération. Mais puisqu'un queue utilise un deque comme contenant sous-jacent, pourquoi ne pas utiliser un deque directement?

#include <iostream>
#include <queue>
using namespace std;

int main() {
  deque<int> q;
  q.push_back(1);
  q.push_back(2);
  q.push_back(3);
  for(deque<int>::iterator it = q.begin(); it != q.end(); ++it)
    cout << *it << endl;
}

réponse similaire pour une file d'attente prioritaire: Non, vous ne pouvez pas. Dans ce cas, un vector est utilisé par défaut. Dans aucun des cas vous ne pouvez accéder au conteneur sous-jacent pour itérer au-dessus d'eux. Voir cette question pour poursuite de la lecture.

11
répondu marcog 2017-05-23 12:34:26

, Vous pouvez le faire de cette façon - bam! Notez que les articles ne sont pas nécessairement dans l'ordre "trié" alors qu'ils sont dans la file d'attente, au moins en ce qui concerne une itération simple du conteneur.

#include <queue>
#include <cstdlib>
#include <iostream>
using namespace std;

template <class T, class S, class C>
S& Container(priority_queue<T, S, C>& q) {
    struct HackedQueue : private priority_queue<T, S, C> {
        static S& Container(priority_queue<T, S, C>& q) {
            return q.*&HackedQueue::c;
        }
    };
    return HackedQueue::Container(q);
}

int main()
{
    priority_queue<int> pq;
    vector<int> &tasks = Container(pq);

    cout<<"Putting numbers into the queue"<<endl;
    for(int i=0;i<20;i++){
        int temp=rand();
        cout<<temp<<endl;
        pq.push(temp);
    }

    cout<<endl<<"Reading numbers in the queue"<<endl;
    for(vector<int>::iterator i=tasks.begin();i!=tasks.end();i++)
        cout<<*i<<endl;

    cout<<endl<<"Taking numbers out of the queue"<<endl;
    while(!pq.empty()){
        int temp=pq.top();
        pq.pop();
        cout<<temp<<endl;
    }

    return 0;
}
11
répondu Richard 2014-09-08 10:15:19

priority_queue ne permet pas l'itération à travers tous les membres, probablement parce qu'il serait trop facile d'invalider l'ordre de priorité de la file d'attente (en modifiant les éléments que vous traversez) ou peut-être que c'est un "pas mon travail" raisonnement.

le contournement officiel est d'utiliser un vector à la place et de gérer vous-même la priorité avec make_heap , push_heap et pop_heap . Une autre solution, dans la réponse de @Richard, consiste à utiliser une classe dérivée de priority_queue et accéder au stockage sous-jacent qui a une visibilité protected .

9
répondu xan 2013-11-30 19:45:31

oui, faites une copie de priority_queue et itérez-la.

4
répondu Lie Ryan 2010-12-19 20:32:48

ce n'est pas possible. Vous devriez utiliser un autre contenant, probablement un deque vous servirait le mieux.

3
répondu Björn Pollex 2010-12-19 19:54:36
#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    pq.push_back(1);
    pq.push_back(2);
    pq.push_back(3);

    std::priority_queue<int> temp = pq;

    while (!temp.empty()) {
        std::cout << temp.top() << std::endl;
        temp.pop();
    }

    return 0;
}
2
répondu Snooze 2016-08-31 19:55:05
Les Files d'attente

sont totalement différentes des vecteurs et sont utilisées à des fins différentes. Les files d'attente prioritaires sont simplement triées deques sans accès direct à l'arrière. Cependant, si vous voulez désespérément faire cela pour n'importe quelle méthode, ce que vous pouvez faire est pop off l'élément top/front, l'ajouter à une liste/tableau/vecteur, et puis pousser l'élément de nouveau dans votre file d'attente pour(size_t i = 0; i < Q. size (); i++). J'ai suivi un cours sur les structures de données java, et c'était la réponse à une question d'examen. De Plus il est la seule méthode que je pense.

1
répondu sj755 2010-12-22 03:17:26

j'ai trouvé ceci après avoir trébuché sur votre question. Il existe une façon très simple de le faire en écrivant une implémentation héritant de std::priority_queue. C'est tout de 14 lignes.

http://www.linuxtopia.org/online_books/programming_books/c++_practical_programming / c++_practical_programming_189.html

1
répondu Jonathan Henson 2013-04-08 03:43:49

j'avais moi-même la même question. J'ai trouvé qu'il était très difficile, voire impossible, d'accéder à la structure de données sous-jacente à la file d'attente des priorités. Dans mon cas, cela a été un vecteur d'objets.

cependant, j'ai fini par utiliser un tas de bibliothèque standard. Il est presque aussi facile qu'une file d'attente prioritaire (il faut deux instructions pour pousser et pop, contre 1 pour le pq), sinon le comportement semble être identique et Je peux accéder à la structure de données sous-jacente si Je ne modifie pas il.

0
répondu David E. 2014-01-27 15:05:20

C++ priority_queue n'offre pas une .begin () pointer (comme vector le ferait) que vous pouvez utiliser pour itérer dessus.

si vous voulez itérer au-dessus de la file d'attente de priorité pour chercher si elle contient une valeur alors peut-être créer une file d'attente de priorité de wrapper et utiliser un jeu de hachage pour garder une trace de ce que vous avez dans la file d'attente.

class MyPriorityQueue {

   MyPriorityQueue() {}

   void push(int item) {
     if (!contains(item)){
       pq_.push(item);
       set_.emplace(item);
     }
   }
   void pop() {
     if (!empty()) {
       int top = pq_.top();
       set_.erase(top);
       pq_.pop();
     }
   }
   int top() { return pq_.top(); }
   bool contains(int item) { return set_.find(item) != set_.end(); }
   bool empty() const { return set_.empty(); }

 private:
   std::priority_queue<int> pq_;
   std::unordered_set<int> set_;
};
0
répondu mario 2017-05-31 17:13:42

bon nombre de ces réponses reposent sur le codage/l'utilisation de nombreuses fonctionnalités arcanes C++. C'est pas grave, on s'amuse et on finance des programmeurs hors de prix. Une solution directe qui est rapide, Pas Cher à programmer mais plus cher à exécuter, est:

// 
// Only use this routine when developing code, NOT for production use!!
//
// Note. _pq is in private for a class that uses the priority queue
// and listQueue is a public method in that same class.
//
void listQueue() {

    // allocate pointer to a NEW container
    priority_queue<int>* new_pq = new  priority_queue<int>;

    while (!_pq->empty()) {

        int el = _pq->top();

        cout << "(" << el << ")" << endl;

        new_pq->push(el);

        _pq->pop();

    } // end while;

    // remove container storage
    delete(_pq);

    // viola, new container same as the old
    _pq = new_pq;

} // end of listQueue;

soit dit en passant, il semble parfaitement non-raisonnable de ne pas fournir un itérateur pour une priority_queue, surtout quand il s'agit d'une classe de conteneur pour une structure ou.

0
répondu JackCColeman 2017-09-17 19:54:47

pour les besoins de base, un std::multiset vous donnera des propriétés similaires, mais avec la capacité d'itérer:

  • Éléments triés, personnalisé Less peut être définie
  • Clés peut se produire plusieurs fois
  • accès rapide et supprimer le premier article
0
répondu AndiDog 2018-05-07 16:06:35

j'ai eu le même problème, où je voulais itérer au-dessus d'une file d'attente prioritaire sans déqueuing (donc détruire ma file d'attente). Je l'ai fait fonctionner pour moi en refondant mon pointeur priority_queue vers un pointeur vers un vecteur (comme mon priority_queue utilise vecteur comme son conteneur). Voici à quoi ça ressemble:

class PriorityQueue {
  private:
    class Element {
    int x; 
    //Other fields
    ...
    ..
    //Comparator function
    bool operator()(const Element* e1, const Element* e2) const {
        // Smallest deadline value has highest priority.
        return e1->x > e2->x;
    }
    };
    // Lock to make sure no other thread/function is modifying the queue
    // Ofcourse we can do our operation w/o lock. if we are sure what is happening in other functions
    pthread_mutex_t lock;   
    std::priority_queue<Element*, std::vector<Element*>, Element> pq;

  public:
    PriorityQueue();
    ~PriorityQueue();
    //print the all the elements of the queue
    void print_queue_elements() {
        std::vector<PriorityQueue::Element*> *queue_vector;
        //Acquire the lock
        pthread_mutex_lock(&lock);
        //recast the priority queue to vector
        queue_vector = reinterpret_cast<std::vector<PriorityQueue::Element*> *>(&pq);
        for(std::vector<PriorityQueue::Element*>::iterator it = (*queue_vector).begin(); it != (*queue_vector).end(); it++) {
            //Assuming Element class has string function
            printf("My Element %s", (*it)->string);
            //other processing with queue elements
        }
        //Release the lock
        pthread_mutex_unlock(&lock);    

    }
    //other functions possibly modifying the priority queue
    ...
    ..
    .
 };

maintenant que j'utilise reinterpret_cast, les gens peuvent discuter de la sécurité du type. Mais dans ce cas je suis sûr de toutes les autres fonctions accéder / changer la file d'attente (qui sont sûr).. et je pense que c'est une bien meilleure façon que de copier le contenu de la file d'attente entière dans un autre conteneur.

Je m'attendais en fait à ce que static_cast fonctionne.. comme priority_queue est adaptateur sur conteneur (vecteur dans notre cas), mais il ne fait pas et j'ai dû utiliser reinterpret_cast .

-1
répondu akshay singh 2012-10-20 05:24:36