Re: [boost] [gsoc] heaps & queues

Subject: Re: [boost] [gsoc] heaps & queues
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-05-06 09:12:40

Sorry I didn't write back sooner... I lost track of the conversation.

> A priority queue is just an adaptor on top of heap
> yes, i know ... heaps can be implemented as container adaptors or as trees
> ...
>

That wasn't really the point I was trying to make. A priority queue isn't a
data structure in its own right. The intent of the project was to develop a
set of heap implementations and possibly implement generic priority_queue
adaptor for them.

> > 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.
>
> do you need mutable priority queues in bgl? and if so, for what data size?
> for small value types, the performance of adaptors should be higher, for
> large ones, the copy/swap overhead may become quite significant. also, i
> have a personal interest in real-time safe priority queues, were i should
> avoid dynamic memory allocation, which is impractical to achieve with
> adaptors.
>

Yes, we do. Typically, the data size will be small (probably 32-128 bits),
but I'm not sure what concerns you're trying to address here. Adaptors like
stack, queue, or std::priority_queue have virtually no overhead whatsoever
because of inlining and copy elision.

The underlying heap implementations may incur overhead based on the number
of copies and swaps, and occasional allocations, but that's generally
unavoidable (depending on your heap implementation). The cost of copies
depends entirely on the data type being put into the heap. You don't have
any control over that.

I would defer issues about real-time, safe priority queues until later.

> > 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.
>
> this approach is not too different from dietmar kuehl's pri_queue. however
> i
> personally found it not too practical to use. boost/pending/mutable_queue
> uses a map as member of the data structure, which is not really straight-
> forward to use, either ...
>

I agree. Also, the implementation is written in terms of property maps,
which are a fairly unwieldy abstraction that nobody really seems to
understand.

> but is your code available? i'd like to have a closer look at the
> implementation ...

I'll try to dig it out in the next day or two and send you an email
off-list.

Andrew Sutton
andrew.n.sutton_at_[hidden]