[boost] [intrusive] More features for treap?

Subject: [boost] [intrusive] More features for treap?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-10-20 09:16:51

Dear All,

I've been looking at Boost.Intrusive's treap, and finding that
it doesn't quite do what I need.

Here's an example: say I have data about earthquakes in the form
(date, magnitude, description).  I can store that in a treap
with date as the key and magnitude as the priority.  Now I'd
like to be able to do operations like:

- Find the strongest earthquake between dates A and B.
- Iterate over all the earthquakes with magnitude > X in date order.
- For each year (or month, or decade etc) find the strongest quake.

The first two are straightforward in a treap, but the current
Boost.Intrusive API doesn't (AFAICT) let me do it.  (The third
one is less obvious.)

I have been wondering how the API could most easily be extended
to support this sort of thing, and I'm coming to the conclusion
that it is probably best to expose the actual tree structure so
that the algorithms for these operations can be implemented
explicitly by the user code.  I have had similar thoughts in the
past about other trees i.e. augmented trees to implement interval
trees; the choice is either (a) implement these things inside
Boost.Intrusive; (b) don't use Boost.Intrusive at all; (c) extend
the intrusive API to expose the actual tree structure.  In cases
like these extensions to treap, the new operations are simple
compared to the complexities of inserting and erasing elements;
being able to use the existing implementations of those operations
while adding other (non-mutating?) features would save a lot of
work.

Any thoughts anyone?

(Is anyone else using treap?)

Regards,  Phil.