How to iterate over a priority_queue?

Can I traverse a standard priority_queue or standard queue in c++ with an iterator (like a vector)? I don't want to use pop because it cause my queue to be dequeued.

Thanks for any help

priority_queue doesn't allow iteration through all the members, presumably because it would be too easy in invalidate the priority ordering of the queue (by modifying the elements you traverse) or maybe it's a "not my job" rationale.

The official work-around is to use a vector instead and manage the priority-ness yourself with make_heap, push_heap and pop_heap. Another work-around, in @Richard's answer, is to use a class derived from priority_queue and access the underlying storage which has protected visibility.

You can do it like this - bam! Notice that items are not necessarily in "sorted" order while they are in the queue, at least with regards to a straight-forward iteration of the container.

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

A queue purposefully provides a limited interface, which excludes iteration. But since a queue uses a deque as the underlying container, why not use a deque directly?

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

Similar answer for a priority queue: no, you cannot. In this case though, a vector is used by default. In neither case can you access the underlying container to iterate over them. See this question for further reading.

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

Yes, make a copy of the priority_queue and iterate over that.

This is not possible. You would have to use a different container, probably a deque would serve you best.

I found this after stumbling across your question. There is a very simple way of doing this by writing an implementation inheriting from std::priority_queue. It is all of 14 lines.

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

Queues are totally different from vectors and are used for different purposes. Priority queues are simply sorted deques with no direct access to the back. However, if you desperately want to do this for whatever method, what you can do is pop off the top/front element, add it to a list/array/vector, and then push the element back into your queue for(size_t i = 0; i < q.size(); i++). I took a class in java data structures, and this was the answer to an exam question. Plus it is the only method i can think of.

Many of these answers rely on coding/using many of C++ arcane features. That's ok, fun and funds expensive programmers. A direct solution that is quick, cheap to program but more expensive to run, is:

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

By the way, it seems perfectly non-sensible to NOT provide an iterator for a priority_queue, especially when it is a container class for a or structure.

https://stackoverflow.com/questions/16749723/how-i-can-find-value-in-priority-queue almost same. The container is protected, use this trick to access it.

c++ version >=11

#include<iostream>
#include<queue>
using namespace std;
template<class T, class C = vector<T>, class P = less<typename C::value_type> >
struct heapq :std::priority_queue<T,C,P> {
    using priority_queue<T,C,P>::priority_queue;
    typename C::iterator begin() { return std::priority_queue<T, C, P>::c.begin(); }
    typename C::iterator end() { return std::priority_queue<T, C, P>::c.end(); }
};
int main(){
    heapq<int> q;
    q.push(100);
    q.push(80);
    q.push(60);
    for(auto e:q) cout<<e<<endl;
}

C++ priority_queue does not offer a .begin() pointer (like vector would do) that you can use to iterate over it.

If you want to iterate over the priority queue to search for whether it contains a value then maybe create a wrapper priority queue and use a hash set to keep track of what you have in the queue.

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

For basic purposes, a std::multiset will give you similar properties but with the ability to iterate:

• Items sorted, custom Less can be defined
• Keys can occur multiple times
• Quick to access and remove first item

I had the same question myself. I found it was very difficult, maybe impossible, to get to the data structure underlying the priority queue. In my case this was a vector of objects.

However, I ended up using a standard template library heap. It is almost as easy as a priority queue (it takes two instructions to push and pop, vs. 1 for the pq), otherwise the behavior seems to be identical and I can get at the underlying data structure if I don't modify it.

If you want to push items in an ordered manner with complexity (logN). But would like to iterate over the elements as well in increasing order, you can use set<int>. Sets are typically implemented as binary search trees.

Sets are iterable (begin, end, rbegin, rend etc)

I had the same problem, where I wanted to iterate over a priority queue without dequeuing (hence destroying my queue). I made it work for me by recasting my priority_queue pointer to a pointer to a vector (as my priority_queue uses vector as its container). Here is how it looks like:

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

Now since I am using reinterpret_cast, people can argue about type-safety. But in this case I am sure about all other functions accessing/changing the queue (all of which are safe).. and I feel this is a much better way than copying the content of whole queue to some other container.

I was actually expecting static_cast to work.. as priority_queue is adaptor over container (vector in our case), but it doesnt and I had to use reinterpret_cast.