Subject: [boost] [gsoc] heaps & queues
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-04-28 14:55:30
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_at_[hidden] 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.