On 18/01/13 19:27, Vadim Stadnik wrote:
On Sat, Jan 19, 2013 at 3:17 AM, Phil Endecott < spam_from_boost_dev@chezphil.org> 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