Boost logo

Boost :

Subject: Re: [boost] [heap] A few questions
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-10 16:02:25

Andrew Hundt wrote:
> 1) Is it possible to iterate through the heap in order of priority with an
> iterator?

No - but the question raises an interesting issue.

If you want to iterate in-order through an entire heap efficiently, you
should sort the underlying sequence using std::sort_heap and then
iterate through the result. Clearly that's incompatible with providing
a simple iterator interface.

You might want those iterators so that you can iterate through just a
small part of the heap. For example, I have some code that uses
std::partial_sort to sort just enough of a large std::vector to satisfy
current requirements; this is used to display a scrollable list of
search results, where the common case is that the user only looks at
the first screenful (PSEUDO_CODE):

template <typename T>
class vector_sorted_on_demand {
   std::vector<T> impl;
   size_t n_sorted;
   void push_back(const T& val) {
     n_sorted = 0; // This suits the case where everything is added
before anything is read.
   T operator[](size_t idx) {
     if (idx >= n_sorted) {
       size_t n_to_sort = n_sorted/2 + 10; // or whatever
       size_t mid = std::max( idx, std::min(n_sorted + n_to_sort,
impl.size()) );
       std::partial_sort(impl.begin()+n_sorted, impl.begin()+mid, impl.end());
       n_sorted = mid;
     return impl[idx];

I could imagine instead maintaining the unsorted portion as a heap,
with some complexity trade-offs.

It seems to me that this sort of thing is best done using an explicit
"underlying container" i.e. std::vector, with algorithms on top of it.
A heap container with iterators just doesn't seem such a good fit: it
maintains the heap predicate safely, but I don't always want that.

This makes me wonder whether Tim's proposed alternative heap structures
should perhaps be decomposed slightly, to expose algorithms in the
style of std::push|pop_heap. Without that, I can't use e.g. the b_heap
in this style of "part heap, part sorted" hybrid container. Is
extracting algorithms practical?

Regards, Phil.

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