Boost logo

Boost :

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.


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


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at