C++ - interval tree implementation

Question

Does someone know any good interval tree implementation in C++?

Obviously, something template-driven, better in boost-like style.

And another question - if somebody tested, does a basic std::vector-based interval tree implementation with sorting can beat the generic interval tree (with O(lg) operations) in practice?

Answer 1

I had exactly the same need. I couldn't find any suitable (simple, modern, portable) implementations, so I used a python implementation by Brent Pedersen as a guide and wrote a barebones C++ version. The IntervalTree behaves like a standard STL container, with some caveats due to its simplicity (no iterators, for instance). You use it like this ("T" is an arbitrary type):

vector<Interval<T> > intervals; // ... make intervals! IntervalTree<T> tree(intervals); 

And you query it like this:

vector<Interval<T> > results; tree.findContained(start, stop, results); // results now contains Intervals which are fully contained in the query interval results.clear(); tree.findOverlapping(start, stop, results); // results now contains Intervals which overlap the query interval 

Answer 2

Boost-like ? Boost ICL!

The Boost Interval Container Library