¿Cómo iterar sobre una priority_queue?

¿Puedo atravesar una queue priority_queue estándar o una queue estándar en c ++ con un iterador (como un vector )? No quiero usar pop porque hace que mi cola se elimine.

Gracias por cualquier ayuda

Una queue proporciona a propósito una interfaz limitada, que excluye la iteración. Pero como una queue usa un deque como contenedor subyacente, ¿por qué no utilizar un deque directamente?

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

Respuesta similar para una cola de prioridad: no, no puedes. Sin embargo, en este caso, se usa un vector por defecto. En ninguno de los casos, puede acceder al contenedor subyacente para iterar sobre ellos. Vea esta pregunta para leer más.

Puedes hacerlo así – ¡bam! Tenga en cuenta que los artículos no están necesariamente en orden “ordenado” mientras están en la cola, al menos en lo que respecta a una iteración directa del contenedor.

 #include  #include  #include  using namespace std; template  S& Container(priority_queue& q) { struct HackedQueue : private priority_queue { static S& Container(priority_queue& q) { return q.*&HackedQueue::c; } }; return HackedQueue::Container(q); } int main() { priority_queue pq; vector &tasks = Container(pq); cout<<"Putting numbers into the queue"<::iterator i=tasks.begin();i!=tasks.end();i++) cout<<*i< 

priority_queue no permite la iteración a través de todos los miembros, presumiblemente porque sería demasiado fácil invalidar el orden de prioridad de la cola (modificando los elementos que recorre) o tal vez sea un razonamiento “no es mi trabajo”.

La make_heap oficial es utilizar un vector lugar y administrar la prioridad usted mismo con make_heap , push_heap y pop_heap . Otra alternativa, en la respuesta de @ Richard, es utilizar una clase derivada de priority_queue y acceder al almacenamiento subyacente que tiene visibilidad protected .

Sí, haga una copia de la prioridad_cola e itere sobre eso.

Esto no es posible. Tendría que usar un contenedor diferente, probablemente un deque le serviría mejor.

 #include  #include  int main() { std::priority_queue pq; pq.push_back(1); pq.push_back(2); pq.push_back(3); std::priority_queue temp = pq; while (!temp.empty()) { std::cout << temp.top() << std::endl; temp.pop(); } return 0; } 

Las colas son totalmente diferentes de los vectores y se usan para diferentes propósitos. Las colas de prioridad se clasifican simplemente deques sin acceso directo a la parte posterior. Sin embargo, si desea desesperadamente hacer esto para cualquier método, lo que puede hacer es sacar el elemento superior / frontal, agregarlo a una lista / matriz / vector, y luego insertar el elemento nuevamente en su cola para (size_t i = 0; i

Lo encontré después de tropezar con tu pregunta. Hay una manera muy simple de hacerlo escribiendo una implementación que hereda de std :: priority_queue. Es todo de 14 líneas.

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

Yo tenía la misma pregunta yo mismo. Descubrí que era muy difícil, quizás imposible, llegar a la estructura de datos subyacente a la cola de prioridad. En mi caso, este era un vector de objetos.

Sin embargo, terminé usando un montón de biblioteca de plantillas estándar. Es casi tan fácil como una cola de prioridad (se necesitan dos instrucciones para presionar y abrir, frente a 1 para la pq); de lo contrario, el comportamiento parece ser idéntico y puedo acceder a la estructura de datos subyacente si no lo modifico .

C ++ priority_queue no ofrece un puntero .begin () (como lo haría un vector) que puede usar para iterar sobre él.

Si desea iterar sobre la cola de prioridad para buscar si contiene un valor, entonces tal vez cree una cola de prioridad de envoltura y use un conjunto de hash para hacer un seguimiento de lo que tiene en la cola.

 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 pq_; std::unordered_set set_; }; 

Muchas de estas respuestas se basan en la encoding / uso de muchas de las características arcanas de C ++. Está bien, es divertido y financia a progtwigdores caros. Una solución directa que es rápida, barata de progtwigr pero más costosa de ejecutar, es:

 // // 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* new_pq = new priority_queue; 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; 

Por cierto, parece perfectamente no razonable NO proporcionar un iterador para una prioridad_cola, especialmente cuando se trata de una clase de contenedor para una estructura.

Para propósitos básicos, un std::multiset le dará propiedades similares pero con la capacidad de iterar:

  • Elementos ordenados, personalizados Less se pueden definir
  • Las llaves pueden ocurrir varias veces
  • Rápido acceso y eliminación del primer elemento

Tuve el mismo problema, en el que quería iterar sobre una cola de prioridad sin eliminar (por lo tanto, destruyendo mi cola). Lo hice funcionar para mí al volver a convertir mi puntero priority_queue en un puntero a un vector (ya que mi priority_queue usa vector como contenedor). Así es como se ve:

 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> pq; public: PriorityQueue(); ~PriorityQueue(); //print the all the elements of the queue void print_queue_elements() { std::vector *queue_vector; //Acquire the lock pthread_mutex_lock(&lock); //recast the priority queue to vector queue_vector = reinterpret_cast *>(&pq); for(std::vector::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 ... .. . }; 

Ahora que estoy usando reinterpret_cast, las personas pueden discutir sobre la seguridad de tipo. Pero en este caso estoy seguro de que todas las demás funciones acceden / cambian la cola (todas ellas son seguras) … y creo que esta es una manera mucho mejor que copiar el contenido de la cola completa en algún otro contenedor.

De hecho, esperaba que static_cast funcionara, ya que priority_queue es adapter over container (vector en nuestro caso), pero no funciona y tuve que usar reinterpret_cast .