Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk