Is there a way to iterate over a priority queue in c++ ? My understanding is that they are more or less immutable and the only manipulation of the container is to the top element. I would like to be able to print out the contents of a priority queue but am unsure of how to even approach the problem.
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority.
A descending order priority queue gives the highest priority to the highest number in that queue. For example, you have six numbers in the priority queue that are 4, 8, 12, 45, 35, 20. Firstly, you will arrange these numbers in ascending order. The new list is as follows: 45, 35, 20, 12, 8, 4.
The priority queue (also known as the fringe) is used to keep track of unexplored routes, the one for which a lower bound on the total path length is smallest is given highest priority. Heap Sort : Heap sort is typically implemented using Heap which is an implementation of Priority Queue.
A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first. However, if elements with the same priority occur, they are served according to their order in the queue.
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;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With