<p>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.</p>

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