Re: [boost] Review managers wanted for augmented data structures

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2013-03-03 06:00:32

On Sun, Mar 3, 2013 at 11:57 AM, Vadim Stadnik <vadimstdk_at_[hidden]> wrote:
> On Sun, Mar 3, 2013 at 1:21 AM, Martin Knoblauch Revuelta <
> mkrevuelta_at_[hidden]> wrote:
>
>> > [...]
>
> It looks like you already gained quite significant experience in this area.
> Do you know any other reasons and/or concerns why augmented data structures
> should NOT be added to STL?

The main concern is the balance between the value they add and their cost.

On one hand, which are the real-life applications where these
containers would really help? In my opinion, the programming community
has learned to solve zillions of problems with arrays, lists, search
trees, heaps and hash tables. Now it's not easy to find a real-life
problem where augmented trees provide a significantly faster solution.
Though, they may allow amazingly simple, non-tuning, easier-to-code,
solutions.

On the other hand, in addition to the usual bloat, there is a deep
concern regarding the possible incorrect use of these sequence
containers. Lazy unexperienced programmers might misuse them as an
all-purpose replacement of vector and list.

If the standard library adopted them, it would be somehow advocating
their use. If there were no real-life applications, then it would be
advocating inefficiency.

> [..]
> The discussion of augmented trees by Boost community is particularly
> interesting.
> Do you know if there was a formal Boost review of any variant of augmented
> data structures and/or containers?

There was an interesting discussion when I proposed it:

http://boost.2283326.n4.nabble.com/proposal-Sequence-container-with-O-log-n-random-access-and-O-log-n-insertion-removal-wherever-td2615747.html

http://boost.2283326.n4.nabble.com/proposal-Rank-List-old-name-AVL-Array-in-the-Sandbox-Vault-td2617382.html#a2617384

> [..] I proposed for the Boost
> review array based augmented B+ trees and decided to postpone the review of
> dynamically allocated augmented B+ trees.

If you only plan to augment the tree with an integer, then this is
perfectly reasonable.

Though, if you plan to augment the trees with a data type that doesn't
support subtraction ---like the interval trees of "Introduction to
Algorithms", or something more complex--- it might be better to stick
to a few children per node. Otherwise, deleting an element might
require a lot of [potentially expensive] additions of a user-defined
type.

Best regards,
Martín Knoblauch Revuelta