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

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2011-11-30 19:26:39

Le 01/12/11 00:41, Vadim Stadnik a écrit :
> 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.

What do you mean on the last sentence?
> 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.
What I mean is that it seems to me that Boost.MultiIndex provides 
already several index for a container, including random access index. 
So, what is exactly the added value.
If your use case can be implemented already using Boost.MultiIndex I 
will consider to propose a specific abstraction on top of 
Boost.Container as it is done in Boost.Bimap. If it is not possible, 
because a specific kind of container must be added to Boost.MultiIndex, 
I will prefer Boost.Multiindex integrates this new container if the use 
case is  of general purpose.

I guess that you could study Boost.MultiIndex to see if your library 
provides something that is not doable with multi-index, or can be done 
better or that improves the performances. I ensure you will not lost 
your time.
> New library can support efficient accumulators through the fast member
> function accumulate() with logarithmic running time in the worst case.
Doesn't accumulate has O(log N) complexity for containers that have 
random access? If not, maybe Boost could include a boost::accumulate 
function that provides this complexity (if not already exists) in a 
non-intrusive way.
> 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.
IIUC you are proposing to store the accumulation of all the lower nodes 
in each node of the container, and maintain this information up to date 
while inserting and removing elements, isn't it?

I have not found a use case for that, but several times I have needed to 
have each node store the accumulation of each one of its children.

I will see this as a possible addition to  Boost.MultiIndex as a special 
container/index that stores the accumulation of the preceding members, 
with the pros and cons. Whether it is worth including this in 
Boost.MultiIndex is an open question, that Joaguin could answer if needed.

Best,
Vicente