On Fri, Dec 2, 2011 at 1:12 AM, Jeff Flinn <Jeffrey.Flinn@gmail.com> 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