Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-09 09:01:54

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_at_[hidden]