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 11:20:53

On Fri, Dec 2, 2011 at 1:12 AM, Jeff Flinn <Jeffrey.Flinn_at_[hidden]> wrote:

> ...
>
>  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?
>

I have included this example, since in my opinion it is an interesting
demonstration that new containers can efficiently solve problems in various
application areas. The example shows the advantage of the implemented STL
extensions. The proposed library can certainly support interval
algorithms. However, at some level the generality of STL interfaces becomes
a limitation in this application area. In my opinion the benefit of
augmented data structures for ICL can be increased through specialized
variants. Please let me know if there is any special interest in interval
algorithms.

Regards,
Vadim Stadnik