Re: std::map<> or std::set<> as interval search tree

Hi all.

I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):

------------+---------+--------+---------+--------
            a x b c d

Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map<>
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.

However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.

So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.

Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a>
and a value x > d returns a value indicating [d,inf>.

Any suggestions?