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
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.
, 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;
}
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
.
ce n'est pas possible. Vous devriez utiliser un autre contenant, probablement un deque
vous servirait le mieux.
#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;
}
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.
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.
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.
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_;
};
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.
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
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
.