
Boost : 
Subject: Re: [boost] [heap] A few questions
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 20110610 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 inorder 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;
public:
void push_back(const T& val) {
impl.push_back(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 tradeoffs.
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::pushpop_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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk