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 01:07:53

Steven Watanabe wrote:
> I'm confused about whether this is a real class and what it's
> actually doing.  Is it actually going to be the base class for the
> different heap implementations?

Yes.  As you can see in PriorityQueue, it's used as a real base class. 
Just an abstract one.

>>>>       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?
> 
> Because it's the language that you're implementing it in.  Consistent
> naming makes it easier to plug in different types (for instance, what if
> I wanted to write a function that could take either your heap or a
> standard priority_queue).  findMin is also inconsistent with standard
> and Boost naming conventions, which use lowercase_and_underscores
> for everything except Concepts and MACROS.

Boost naming conventions are a good reason to change the name.  I 
haven't done my full research on this subject yet, so I simply used my 
own standard camel-case convention.  That said, I still think that the 
naming of the methods should stick to the algorithms rather than the 
STL.  (Just to play the devil's advocate, there should be little or no 
reason to have function take either the STL priority_queue or my heap 
since the d-ary heap and priority_queue should have the same exact 
performance.  Only reason would be if you wanted one of the other heaps, 
in which case pass a heap and forget the priority_queue.)

>>   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.
> 
> If the different names are the only reason to separate PriorityQueue and
> Heap classes, then I'm strongly against it.

Well, it's a different interface, and more importantly allows a 
pluggable structure.  That seems like reason enough to me, but I'm 
certainly open to being persuaded.

 > This is dubious W.R.T. exception safety, because if anything between
 > the change of the value and the call to update throws or if update itself
 > throws, the invariants of the heap will be broken.

This is certainly an issue, and one that has been discussed at length 
previously in the conversation (though not specifically with regard to 
exception safety).  In short, yes.  Any mutability will involve the heap 
properties being violated for a period of time.  This particular 
implementation will rely on the user to be somewhat careful about 
maintaining their updates and, as you pointed out, handling exceptions.

Dan Larkin

Dan Larkin