Subject: Re: [boost] Query of Interest in annotated tree extensions to Boost.Intrusive
From: Jeff Snyder (jeff-boostlists_at_[hidden])
Date: 2013-01-21 09:47:39
On 18/01/13 19:27, Vadim Stadnik wrote:
> On Sat, Jan 19, 2013 at 3:17 AM, Phil Endecott <
> spam_from_boost_dev_at_[hidden]> wrote:
>> "Augmented trees".
> I agree, this and other links in the very first message refer to variants
> of augmented data structures.
> 1. Is there interest in having such functionality in boost?
>> Yes, but we need to get it right. In my opinion, we need something that's
>> sufficiently generic to cover the about-3 use cases.
Absolutely. What I've got currently is generic enough to support all of
these use cases.
>> I'm unclear why this should be added to Boost.Intrusive, rather than being
>> a top-level library in its own right.
An augmented tree library would still have to provide a fully-featured
binary tree, and you can't just write it as a wrapper around another
library's tree implementation.
If my modified Boost.Intrusive were added as a library in its own right,
then Boost.Intrusive itself could just become a wrapper that removed
support for augmentations. I don't see a lot of value in having that split.
I'm not saying that boost.intrusive should gain an augmented-tree-based
interval tree, or countertrees. Those seem like good candidates for
top-level libraries to me, but built upon a container library with
generic support for augmentations.
So, why Boost.Intrusive instead of any other container library?
Ion covered my main reasons for this in his reply.
- There were circumstantial reasons; the project I needed an augmented
tree for also needed it to be an intrusive tree.
- Intrusive containers are the lowest common denominator. Someone
wanting a conventional tree can make do with an intrusive tree, but not
the other way around. This makes the functionality available to the
- Support can easily be extended to non-intrusive containers via
Boost.Container, since it's built upon Intrusive.
- Support for augmented trees can be easily and seamlessly added to
Intrusive's existing API
> Unlike, basic data structures, the augmented data structures can
> efficiently support both copy and move semantics.
> This is why I also wonder why Boost.Intrusive only?
I'm not sure I get the point about copy/move semantics here - how does
augmenting the data structures alter the efficiency of copies and/or moves?
 Except the bits of Intrusive that aren't binary trees
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk