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-11-30 18:41:40

On Thu, Dec 1, 2011 at 3:01 AM, Vicente Botet <vicente.botet_at_[hidden]>wrote:

>
> >>> how is your library related/compared to Boost.MultiIndex?
> >>
> > As far as I understand library multi-index provides multiple views of a
> > collection of data. The submitted containers and data structures can be
> > quite useful at implementation level for this type of applications, since
> > one advanced data structure efficiently supports many types of STL
> > sequences and associative containers.
> >
>
> I don't see how your library could improve the efficiency of
> Boost.MultiIndex. Maybe you could show some figures comparing both
> libraries.
>
> > As for applications to other Boost libraries, I think that in the current
> > shape the new data structures and containers can increase the performance
> > of Accumulators and Interval.
> >
>
> How your library can improve the performance of these libraries?
> Note that I'm not against your library, that I don't know well, but just I
> want to see what is the added value.
>
>
I am not familiar with implementation details of multi-index library. My
reply only concerns the general use of new containers in multi-view
applications. The demonstration  is actually available in the example of
fast counting of intersections of one interval with sequence of intervals.
This solution uses one container, which stores all objects of intervals,
plus two containers, which represent ordered views of lower and upper
endpoints of these intervals. The ordered views support efficient search
operations and provide random access iterators. For this reason the
algorithm of intersection counting has logarithmic running time against
linear time if the solution was based on standard containers. In principle,
the approach can be extended and applied to range queries using multiple
views.

New library can support efficient accumulators through the fast member
function accumulate() with logarithmic running time in the worst case.
Efficient accumulators are not yet implemented in this project. The section
"Iterators and accumulators" of this document

http://dl.dropbox.com/u/51041088/stl_ext_adv_doc/doc/iterators.html

discusses pros and cons of this option. I am not sure whether to add this
functional or not, this is why I ask Boost community if there is an
interest in this functionality.

Regards,
Vadim Stadnik