Finding C++ interval tree algorithm implementation

问题:

This question already has an answer here:

• C++ - interval tree implementation 5 answers

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.

回答1:

I've written a template-based interval tree implementation in C++, https://github.com/ekg/intervaltree. MIT license. Enjoy.

回答2:

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

回答3:

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