Boost logo

Boost :

Subject: Re: [boost] [heap] A few questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-10 13:46:43

> > > > 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?

actually a treap (like boost::intrusive::treap) would be the most efficient data
structure for that.

otoh, one of the ideas behind boost.heap is to emulate a specific functionality
if it is not supported out of the box. e.g. it supports merging of all heaps, no
matter if they can be merged efficiently or not ...


Boost list run by bdawes at, gregod at, cpdaniel at, john at