Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Dan Larkin (danielhlarkin_at_[hidden])
Date: 2010-04-09 00:10:59

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?

>>       virtual void remove( iterator& elem ) = 0;
>>       virtual void update( iterator& elem ) = 0;
> 
> Why is the iterator passed by non-const reference?

It shouldn't be.  I got tied up a bit in the different levels of 
dereferencing in my head and was thinking const references wouldn't 
allow me to do what was needed.  I blame it on the algorithms exam I 
just took frying my brain a little too much for one night.

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

>> <snip>
>>       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

Dan Larkin