Reputation: 931
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
Upvotes: 93
Views: 123046
Reputation: 861
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 :
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)
.
Upvotes: 3
Reputation: 21
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 << " ";
}
}
Upvotes: 1
Reputation: 1165
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)
Upvotes: 0
Reputation: 70249
For basic purposes, a std::multiset
will give you similar properties but with the ability to iterate:
Less
can be definedUpvotes: 1
Reputation: 3807
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.
Upvotes: 2
Reputation: 11
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_;
};
Upvotes: 1
Reputation: 519
#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;
}
Upvotes: 13
Reputation: 61577
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;
}
Upvotes: 30
Reputation: 89
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.
Upvotes: 0
Reputation: 7731
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.
Upvotes: 43
Reputation: 8206
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.
Upvotes: 3
Reputation: 71
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
.
Upvotes: -1
Reputation: 4072
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.
Upvotes: 2
Reputation: 138547
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.
Upvotes: 10
Reputation: 76886
This is not possible. You would have to use a different container, probably a deque
would serve you best.
Upvotes: 3