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

From:

Seungbeom Kim <musiphil@bawi.org>

Newsgroups:

comp.lang.c++.moderated

Date:

Thu, 18 Sep 2008 15:28:55 CST

Message-ID:

<gap7q7$eui$1@news.stanford.edu>

Rune Allnor wrote:

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?

Here's the code that does it:

     std::ostream& os = std::cout;

     typedef std::set<int> set;
     typedef set::const_iterator citer;

     set s;
     s.insert(2);
     s.insert(4);

     for (int x = 1; x <= 5; ++x) {
         citer i = s.upper_bound(x);
         os << x << '\t';
         if (i == s.end()) {
             citer j = i; --j;
             os << '[' << *j << ", +inf)";
         }
         else if (i == s.begin())
             os << "(-inf, " << *i << ')';
         else {
             citer j = i; --j;
             os << '[' << *j << ", " << *i << ')';
         }
         os << '\n';
     }

Result:

     1 (-inf, 2)
     2 [2, 4)
     3 [2, 4)
     4 [4, +inf)
     5 [4, +inf)

By the way, an alternative version:

     for (int x = 1; x <= 5; ++x) {
         citer i = s.lower_bound(x);
         os << x << '\t';
         if (i == s.end()) {
             citer j = i; --j;
             os << '(' << *j << ", +inf)";
         }
         else if (x == *i)
             os << *i;
         else if (i == s.begin())
             os << "(-inf, " << *i << ')';
         else {
             citer j = i; --j;
             os << '(' << *j << ", " << *i << ')';
         }
         os << '\n';
     }

gives the following, more specific result:

     1 (-inf, 2)
     2 2
     3 (2, 4)
     4 4
     5 (4, +inf)

--
Seungbeom Kim

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]