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.