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

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Jeff Flinn (Jeffrey.Flinn_at_[hidden])
Date: 2011-12-01 09:12:50

Vadim Stadnik wrote:
> On Thu, Dec 1, 2011 at 11:26 AM, Vicente J. Botet Escriba <
> vicente.botet_at_[hidden]> wrote:
...
>>>>  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.
...
>>  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.
...
> Can multi-index library solve the problem of counting of intersections of
> one interval with an arbitrary sequence of intervals in O(log N) time and
> provide the same running time for update operations?
> The proposed library can support this efficiency, since its containers have
> logarithmic cost of find, insert and erase operations and random access
> iterator for both ordered and un-ordered data.

Your example at least looks like some overlap with Boost ICL, the 
Interval Container Library. Or is that what you were referring to above 
when you mentioned the Boost Interval library?

Jeff