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: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-01-22 06:54:23

On Tue, Jan 22, 2013 at 12:47 AM, Jeff Snyder <
jeff-boostlists_at_[hidden]> wrote:

>
>  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?
>
>
My question was mostly concerning copy semantics. Intrusive containers do
not store copies of values and they are not copyable, but copy semantics is
must for STL compliant containers and for many C++ algorithms. Ion and you
have already explained how it can be achieved with Boost.Container.

For trees the group of move semantics functions and operations includes not
only swap, but also join and split. The last two operations provide more
efficient support for STL interfaces in augmented data structures than in
basic ones, since they avoid linear time re-counting of moved elements.
Copying one element and moving any number of consecutive elements have in
theory the same logarithmic complexity. Thus, intrusive containers should
benefit from augmented trees. This is a predictable advantage.

Regards,
Vadim Stadnik