Re: std::map<> or std::set<> as interval search tree
on Sun Aug 31 2008, Rune Allnor <allnor-AT-tele.ntnu.no> wrote:
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>.
There's something called an "interval tree." IIRC it stores each
interval by its start position and annotates each node additionally with
the maximum end position of all its descendant nodes. I implemented one
years ago with minor modifications of STLPort's rbtree implementation
that underlay its associative containers. Ah, yes:
On the other hand, that's allows overlapping intervals, and it looks
like your example doesn't have overlaps. If not, you could use one of
the std associative containers (or a sorted vector) with a key that is
the beginning of each interval, and use upper_bound to find the position
where x falls in the sequence. I leave dealing with the endpoints as an
exercise for the reader ;-)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]