 # Boost :

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) {}
};

}