Re: [boost] [gsoc] heaps & queues

Subject: Re: [boost] [gsoc] heaps & queues
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-28 20:04:38

>
> i'm the student, working on the heaps&queues project during this year's
> summer of code. i have also been in touch with my mentor about this, but
> thought, it may be a good idea to hear some comments from other boost devs.
>

I might as well chime in since I wrote the original project description :)

A priority queue is just an adaptor on top of heap (or other "sorted" data
structure) -- at least that's my understanding. For example, the
std::priority_queue sits on top of a vector (usually) with some special
algorithms for push and pop.

If you encapsulate that logic as a binary_heap (or maybe flat_heap, if I
adopt the Boost.Container notation), then you can effectively decouple the
queue from the heap.

> i would like to implement the priority queue data as intrusive data
> structures, which can simply be wrapped to non-intrusive ones. the main
> reason for this approach is the mutable property.
>

I think there's a better solution that doesn't require writing intrusive
data structures. Not that this is a bad idea, but it's overhead that I'm not
looking for in the BGL.

Make the user keep user keep track of that information by having push_heap
return an iterator and writing an update that takes an iterator, updating
the referenced object's position in the heap. If I want, I can track those
in an unordered map, if I don't want it, I don't care. I wrote a prototype a
couple months ago by modifying the GCC push_heap algorithm. It worked pretty
well.

The intrusive solution is a good idea also. Maybe both?

> the question then would be, whether i should try to introduce it into
> boost.intrusive, or implement it as a library on its own. boost.intrusive
> already provides a treap, so it would be quite logical to include heap data
> structures as well. otoh, having a heap library with both intrusive and
> non-
> intrusive data structures, one would have everything in one place. so, i
> see
> benefits in both approaches, but would like to hear, what other people
> think
> about it ...
>

I think Intrusive or Container (in the review queue) are probably good
targets, depending on what you decide to do.

Andrew Sutton
andrew.n.sutton_at_[hidden]