hi all, 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 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. in order to provide a mutable priority queue, one would either need a handle to the inner node (like in dietmar kuehl's pri_queue) or provide a lookup table (as in boost/pending/mutable_queue). both approaches are somehow problematic. otoh, if i want to change the priority of a node, it would be natural to use an intrusive data structure for this. the non-intrusive version would be simply a wrapped version of the intrusive implementation, and would simply lack the mutable property. 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 ... cheers, tim -- tim@klingt.org http://tim.klingt.org The first question I ask myself when something doesn't seem to be beautiful is why do I think it's not beautiful. And very shortly you discover that there is no reason. John Cage.
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@gmail.com
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@klingt.org 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
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@gmail.com
participants (2)
-
Andrew Sutton -
Tim Blechmann