Search for C ++ Interval Tree Algorithm Implementation

Question

I am trying to find an efficient C ++ interval tree implementation (mostly, probably based on red black trees) without a virus or restrictive license. Any pointers to an easy standalone implementation? For the use case, I mean that the set of intervals is known from the very beginning (say, a million), and I want to be able to quickly get a list of intervals that span a given interval. Thus, the tree, once built, will not change - just need quick queries.

Answer 1

I wrote an interval tree template based on templates in C ++, https://github.com/ekg/intervaltree . MIT License. Enjoy it.

Answer 2

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

In fact, I can’t think about how to deal with this more efficiently than supporting std :: map pairs and passing these pairs of iterators to upper_bound() and lower_bound() . You want the pairs of iterators contained in the map itself, so that you can easily get zero, depending on which pairs are likely to be in the interval (if the initial iterator in the "candidate interval" comes after the end of this interval, you look, then you can skip checking that - and all subsequent ones - pairs of iterators).

Answer 3

There is also a C # implementation of the interval tree in this link . It's easy enough to translate to C ++ for those in need.