Steven Watanabe wrote:
Maybe I missed something but why pure virtual functions?
Heap is simply a concept, and should be treated as an abstract base class, I believe, and should never be instantiated. Individual models should take up all the slack of actually implementing these methods. Do I have the wrong understanding?
I know that Steven addresses some of the issues in previous emails, but I thought I'd also add my own suggestion. Forget about concepts and abstract classes for now. Let each kind of heap be its own heap. If you try to over-generalize too early, you'll probably end up writing a lot of weird adaptive corner cases. After you have the
virtual iterator& findMin() = 0;
virtual void removeMin() = 0;
top and pop would be more consistent with std::priority_queue.
findMin and removeMin (or even moreso deleteMin) are more consistent with standard heap terminology. It's a well-known group of data structures taught in curricula all over and studied since who knows when. Why conform to the terminology of a specific implementation in a programming language that's not nearly as old or well-established? I'm providing the PriorityQueue class as essentially a wrapper with the potentially more appealing push/pop terminology for this reason. Sorry if that sounded overly aggressive, it wasn't my intent.
Because using greater<> as a comparator instead of less<> changes the semantics of "min" to the semantics of "max", which makes findMin and removeMin a little disingenuous at best. Really, the "top" of the heap is either the min or max depending how the heap is parameterized. You could probably make a case for "remove" instead of "pop", since heaps aren't really queue's unless they're being used as priority queues.
virtual iterator& begin() = 0;
virtual iterator& end() = 0;
How can these possible return a /reference/ to an iterator?
This was a careless mistake on my part. Thank you for calling me on it. :D
Same with insert(). Iterators are almost always passed by value, and if you're not passing by value then you probably need to make a very compelling case for not doing so. Welcome to Boost :) I hope we're not discouraging you. This is very good discussion. Andrew Sutton andrew.n.sutton@gmail.com