Re: [boost] [stl_ext_adv] ] Interest in advanced data structures

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2011-12-01 07:30:16

On Thu, Dec 1, 2011 at 9:42 PM, Thorsten Ottosen <
thorsten.ottosen_at_[hidden]> wrote:

> Den 30-11-2011 10:58, Vadim Stadnik skrev:
>
>  Hi all,
>>
>> Advanced data structures (ADS) offer useful STL extensions that are not
>> possible or not efficient with basic data structures, such as arrays,
>> linked lists and red-black trees.
>>
>
> I'm interested. In particular, if the library can be integrated seamlessly
> with Boost.Accumulators and other libs, it seems very interesting.
>
Thank you for the interest.

At the moment I think that the best option is to provide access to the
proposed data structures through STL interfaces, since they maximizes
usefulness of these data structures. The other options are the development
of specialized data structures or adding specialized interface functions to
the existing classes. Let me know what kind of functionality is not
supported yet to have a better understanding of the specific problems.

Are there variations of the trees that allow for other types of fast
> queries than just accumulate? If so, then there might be a generic way to
> incorporate them.

Yes, you are right.
The augmented B+ trees are widely used in solutions to various problems of
computational geometry. However, I think that this area is not general
enough for Boost libraries, this is why it is out of scope of this project.

In principle there are many other solutions which can benefit from
augmented data structures. I have a number of ideas as for future
development, but I am not sure if they are really useful for Boost users
and developers. This is why I asked Boost community about most interesting
and useful applications for the augmented data structures.

A generalized implementation of augmented data structures is possible. It
is also possible that such implementation can be based on a simpler
topology and data scheme than those used in the proposed library. However,
as usual a generalization involves some risk of not optimized support for
specific algorithms. For example, the proposed data structures support not
only the high efficiency of algorithm accumulate(), but also a relatively
high accuracy of this algorithm.

Regards,

Vadim Stadnik