Re: [boost] Query of Interest in annotated tree extensions to Boost.Intrusive

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".
>>
> +1
>
> I agree, this and other links in the very first message refer to variants
> of augmented data structures.

Agreed.

>   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[1] 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 
widest audience.

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

Cheers,
Jeff

[1] Except the bits of Intrusive that aren't binary trees