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
>>> 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
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
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
> 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
> Efficient accumulators are not yet implemented in this project. The section
> "Iterators and accumulators" of this document
> 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.
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk