Re: [boost] [gsoc] heaps & queues

Subject: Re: [boost] [gsoc] heaps & queues
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-04-29 02:35:48

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

yes, i know ... heaps can be implemented as container adaptors or as trees 
...

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

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.

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

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

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

i think, that i should try to implement both intrusive heaps and container 
adaptors. 

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
Most of the trouble in this world has been caused by folks who can't
mind their own business, because they have no business of their own to
mind, any more than a smallpox virus has.
  William S. Burroughs