How to iterate over a priority_queue?

Question

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

Answer 1

Most existing answers either suggest using a different data structure or performing a sequence of O(log n) operations (n being the size of the priority queue). Some even advise to make a copy of the structure.

The operation can be performed in linear time with respect to the number of elements, provided that :

• the underlying container is a vector, and
• it is not necessary to go through the elements in sorted order.

If these conditions are met, the following code can be used :

#include <iostream>
#include <queue>

int main()
{
    using T = int;
    std::priority_queue<T, std::vector<T>, std::less<T>> q;
    
    q.emplace(1); q.emplace(16); q.emplace(5); q.emplace(42); q.emplace(3);
    
    const T* base = &q.top(); // root of the binary heap
    for(size_t i = 0; i<q.size(); i++)
        std::cout << *(base+i)<<" ";
    std::cout << std::endl; // outputs "42 16 5 1 3"

    return 0;
}

This approach has the advantage of not changing the data structure used : if a binary heap is suited for your application, there is no point in using a multiset. Also it is compact, trivial to implement, does not change the original object and does not require additional memory. Finally, it runs in O(n) time instead of the commonly seen O(n log n).

Answer 2

Making a copy and iterating over that - suggested by @lie-ryan

#include <iostream>
#include <queue>

using namespace std;
void make_copy(priority_queue<int, vector<int>> pq, vector<int> &arr)
{
    arr = {}; // if it was not empty , make it :)
    while (!pq.empty())
    {
        arr.push_back(pq.top());
        pq.pop();
    }
}
int main()
{
    priority_queue<int, vector<int>> q;
    q.push(1);
    q.push(2);
    q.push(3);
    vector<int> arr;
    make_copy(q, arr); // this will copy all elements of q to arr :)
    for (auto &x : arr)
    {
        cout << x << " ";
    }
}

Answer 3

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)

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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

Answer 12

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.

Answer 13

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.

Answer 14

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

Answer 15

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.

Answer 16

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