reusing std::lower_bound

From: Craig Hicks (hicks_at_[hidden])
Date: 2001-02-28 09:13:42

Hello

I needed to do a binary search over an interval of numbers, and I thought it
would be nifty to
use std::lower_bound() to perform the search part, while I supplied an
appropriate functional
to supply the condition.

There exists an application specific functional

struct Lt_fn
{
    // Application specific data members commented out
    bool operator() (int i, void*);
};

which is assumed to evaluate to satisfy

Lt_fn().(i, (void*)0) == true    for n0 <= i  < nn
Lt_fn().(i, (void*)0) == false    for nn <=  i  < n1

and I want to find the lower bound (nn) for the false condition.
Calls to Lt_fn()(...) are expensive so I try to minimize the number of
calls by using std::lower_bound which employs an efficient binary search,
as follows

    Lt_fn lt_fn;
    // application specific setting of lt_fn members
    int i_false_lb = *std::lower_bound
        (stdex::integer(n0), stdex::integer(n1), (void*)0, lt_fn);

Writing the class "stdex::integer" was the price paid for reusing the STL
binary search algorithm.
The definition is included at the end, since it takes up screen space.

I wonder if something like stdex::integer already exists in the boost
library for just this purpose,
or if perhaps there is another containerless way which I couldn't see.

Regards,

    Craig Hicks
   KGK Ltd, Tokyo Japan

namespace stdex
{

struct integer
    : public std::iterator <random_access_iterator_tag, int>
{
    int i;
    int& operator * () { return i; }
    const int& operator * () const { return i; }

    integer& operator += (int n) { i+=n; return *this;}
    integer& operator -= (int n) { i-=n; return *this;}

    integer operator + (int n) { integer s=*this; i+=n; return *this; }
    integer operator - (int n) { integer s=*this; i-=n; return *this; }

    difference_type operator - (const integer& s) { return i-s.i; }

    integer& operator ++ () { ++i; return *this; }  // pre
    integer operator ++ (int) { integer s=*this; ++i; return s;} // post

    integer& operator -- () { --i; return *this; }  // pre
    integer operator -- (int) { integer s=*this; --i; return s;} // post

    integer& operator = (int n) { i=n; return *this; }

    integer(int n) : i(n) {}
    integer(const integer& s) : i(s.i) {}
    integer() : i(0) {}
};

}