How to Iterate Over a Priority_Queue

Priority Queues in c++

The underlying container is a protected data member named c (see here for further details). Therefore you can always inherit from a std::priority_queue and export a couple of iterators over that container (if available).

As a minimal, working example:

#include<queue>
#include<iostream>

struct MyPriorityQueue: std::priority_queue<int> {
    auto begin() const { return c.begin(); }
    auto end() const { return c.end(); }
};

int main() {
    MyPriorityQueue pq;
    pq.push(0);
    pq.push(1);
    for(auto &v: pq) {
        std::cout << v << std::endl;
    }
}

Note: inheriting from data structures in the std:: namespace is usually discouraged.

That being said, it works at least.

---

The code above works in C++14.

Below a slightly modified version that works also in C++11 as requested in the comments:

#include<queue>
#include<iostream>

struct MyPriorityQueue: std::priority_queue<int> {
    decltype(c.begin()) begin() const { return c.begin(); }
    decltype(c.end()) end() const { return c.end(); }
};

int main() {
    MyPriorityQueue pq;
    pq.push(0);
    pq.push(1);
    for(auto &v: pq) {
        std::cout << v << std::endl;
    }
}

Problems with ITERATOR in priority_queue

You can not iterate over a std::priority_queue as this functionality is not provided by its interface.

If you need to be able to iterate over the elements then maybe std::priority_queue is not the right choice of container.

If you want a sorted container that you can iterate over, then perhaps you could use a std::set instead?

std::set<std::pair<int, int>> s;
s.emplace(20, 2);
s.emplace(10, 2);

// Iterate over pairs in sorted order.
for (auto& pair : s) {
    /* ... */
}

Or if you need contiguous data allocation then maybe use a std::vector together with std::sort?

std::vector<std::pair<int, int>> v;
v.emplace_back(20, 2);
v.emplace_back(10, 2);

std::sort(std::begin(v), std::end(v)); // Sort elements.

// Iterate over pairs...
for (auto& pair : s) {
    /* ... */
}

How to iterate over a PriorityQueue?

From the Javadocs

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

There are probably other equivalent mechanisms.

Range based for-loop for priority_queue

No, std::priority_queue does not support the range-based for loop.

The range-based for loop works on arrays and on classes that have begin() and end() member functions. This includes all containers in the C++ standard library as well as std::string (and its basic_string cousins) but not stacks, queues, or priority queues which are container adaptors and do not expose iterators.

How should I iterate a priority queue properly?

Yes, if you need to check every single element in the collection, an iterator or for each is probably best.

Iterator<E> iter = myPriorityQueue.iterator();
while (iter.hasNext()) {
    current = iter.next();
    // do something with current
}

Or

for (Element e : myQueue) {
        // do something with e
}

Iterate and modify c++ priority queue

The standard has functions to help maintain a heap, make_heap, push_heap and pop_heap. Combine those with std::vector or another random access container, and it is not much work to maintain a heap which you can iterate over.

Example:

std::vector<int> heap = {1,3,5,7,9};
std::make_heap(heap.begin(), heap.end());

// add an element
heap.push_back(4);
std::push_heap(heap.begin(), heap.end());

// remove an element
std::pop_heap(heap.begin(), heap.end());
heap.pop_back();

// multiply each element by 2
for (auto & i : heap)
    i *= 2;

Demo

Also note that all the heap functions have an optional parameter for a comparator so that you can control the ordering of your heap.

Iterating vector-based priority_queue

In short, yes.

The standard [priqueue.members] defines the operators on a priority queue in terms of push/emplace/pop_back and heap operations. It is trivial to see that the size of the underlying container will be equal to the size of the priority queue, and that elements will be stored starting from the beginning of the container.

In fact, the standard even guarantees that the underlying container will be a heap as defined by the standard make_heap algorithm.

That said, it is likely worth considering whether or not priority_queue is the best solution for your problem if iteration is required.

---

Related Topics