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;
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 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.