Boost logo

Boost :

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


Andrew Sutton wrote:
> 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

Honestly, I think iterator behavior is the only place where that is even
an issue. The other functions are well-defined for any heap model and
shouldn't be any trouble.

That said, without a unified concept, this project loses most, if not
it's entire, purpose. The concept is almost as important to making the
library useful as having the heaps themselves.

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

Ah, that's a much more compelling argument. I had been having this
argument with myself internally, but decided to stick to the
min-convention due to the default behavior. I think that just won the
case for using top-based vocabulary.

> Welcome to Boost :) I hope we're not discouraging you. This is very good
> discussion.

Not at all. I'd much rather be torn a new one (pardon the imagery) than
coddled. You learn a lot more and get a lot more done that way. Well,
provided it doesn't devolve into a petty flame war that is. ;)

Dan Larkin


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