Range based for-loop for priority_queue

Question

Defining my priority_queue like this,

priority_queue<int> parts(start, start+N, less<int>());

the following code won't compile

for(int t : parts){
    ...
}

Which leads me to question:

In C++11, are range based for loops allowed for std::priority_queue?

In general, which structures are allowed to be iterated trough using a range based for-loop?

I know I can do pretty much the same thing like this:

while(!parts.empty()){
    cout << "Next element: " << parts.top() << endl;
    parts.pop();
}

Is it possible to iterate trough the queue nevertheless?

It isn't the same thing, though. The for loop would iterate over the queue and leave it intact (which is generally not what priority queues are for), but the while loop would empty it. — Fred Larson, Oct 11 '14 at 02:59
@FredLarson +1 for "which is generally not what priority queues are for"; this answers exactly my question. — 0xpentix, Oct 11 '14 at 03:05

score 10 · Accepted Answer · answered Oct 11 '14 at 03:00

10

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.

answered Oct 11 '14 at 03:00

Brian Bi

111,498
10
176
312

1

@pentix Not portably, no. Might I suggest the use of `std::set`? It's not a drop-in replacement, of course, but can do everything a priority queue can with the same asymptotic complexity (constant factor tends to be worse though) – Brian Bi Oct 11 '14 at 03:04
I'll have an eye on `std::set`. I just noticed I could write `parts` as a `std::vector`, `std::sort` it using `std::less`. But this seems be a lot of computation for something that `std::set` seems better for. Thanks ;) – 0xpentix Oct 11 '14 at 03:08
2

@pentix: If you want the behavior and performance of a `std::priority_queue`, and the ability to iterate, you can use a vector along with the heap operations, [`make_heap`](http://en.cppreference.com/w/cpp/algorithm/make_heap), [`push_heap`](http://en.cppreference.com/w/cpp/algorithm/push_heap) and [`pop_heap`](http://en.cppreference.com/w/cpp/algorithm/pop_heap). In fact, that is exactly how `std::priority_queue` is implemented. – Benjamin Lindley Oct 11 '14 at 03:14

Range based for-loop for priority_queue

1 Answers1