Help finding C++ interval tree algorithm implementation

Question

I'm trying to find an efficient C++ interval tree implementation (mostly likely based on red black trees) without a viral or restrictive license. Any pointers to a clean lightweight standalone implementation? For the use case I have in mind, the set of intervals is known at the outset (there would be say a million) and I want to be able to quickly obtain a list of intervals that overlap a given interval. Thus the tree once built will not change -- just needs rapid queries.

Answer 1

The C++ standard library offers red/black trees std::map, std::multimap, std::set and std::multiset.

Really, I can't think of any way to handle this more efficiently than to keep a std::map of iterator pairs, and passing those iterator pairs to upper_bound() and lower_bound(). You'd want the iterator pairs to be kept in a map themselves so that you could easily zero in on which pairs are likely to be in the interval (if the beginning iterator in the "candidate interval" comes after the end of the given interval you're looking at, then you can skip checking that -- and all later -- iterator pairs).

Answer 2

There is a version presented at C++ code for Red-Black Trees And Interval Trees, and a trimmed down implementation at my homepage.