On Fri, Jun 10, 2011 at 11:46 AM, Thomas Klimpel < Thomas.Klimpel@synopsys.com> wrote:
Andrew Hundt wrote:
On Fri, Jun 10, 2011 at 3:07 AM, Tim Blechmann <tim@klingt.org> wrote:
hi andrew,
1) Is it possible to iterate through the heap in order of priority with an iterator?
at the moment it is not possible to iterate the heap in order ... i have been thinking that this may be useful in some cases, however this can only be achieved by increasing the complexity of iterators (in fact every iterator will require a priority queue of possible `next' objects). however it would also simplify heap comparison ...
Also, if one wanted to go through the heap in order of priority in a convenient manner without removing elements it would be very helpful. The simplified heap comparison is definitely an added bonus. I'm also curious how that additional priority queue internal to the iterator would do in terms of memory and runtime performance.
Isn't iteration in order of priority completely opposite to the very idea of a heap (="unordered pile")? If you want/need that, isn't a std::map more suitable for your use case? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I believe a heap is more like a partially ordered pile than an unordered pile. If you are attempting to perform heap sort or perform tasks in order of priority from highest to lowest wouldn't a heap be appropriate? In those cases I was thinking that iterating over the heap in order of priority would make sense as an alternative to calling pq.pop() repeatedly. Such an iterator could make something like copying the contents of the heap into another object such as a vector in sorted order as easy as a call to std::copy(pq.sorted_begin(),pq.sorted_end(),std::back_inserter(vec)). Perhaps an iterator adapter that achieves this effect would be more appropriate? I may be missing something important like a major performance disadvantage or an existing way to accomplish this that is definitively better. However, I don't think a std::map would be appropriate in all cases, since the runtime complexity of various operations of a std::map isn't always the same as the runtime complexity in each heap implementation. Cheers! Andrew Hundt