Re: [boost] associative_vector: request for formal review

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-06-05 00:35:14

On Sun, 4 Jun 2000, David Abrahams wrote:

> > For lower_bound, use
> >    compose_f_gx_hy(m_key_compare, std::identity(), KeyOfValue()));
> > For upper_bound, use
> >    compose_f_gx_hy(m_key_compare, KeyOfValue(), std::identity()));
> >
> > These will work for reasonable implementations of lower/upper_bound.
> >
> > In case of unreasonable implementations or for binary_search, both
> > members are needed.
> 
> Actually, I think according to the standard they must work for all
> conforming implementations. The standard gives no leeway to compute
> lower_bound with comparisons other than as specified by:
> 
> 2 Effects: Finds the first position into which value can be inserted without
> violating the ordering.
> 
> 3 Returns: The furthermost iterator i in the range [ first, last] such that
> for any iterator j in the
> 
> range [ first, i) the following corresponding conditions hold: *j < value or
> comp(*j, value) != false

Note that it is the opposite of the test which a reasonable
implementation will make.  The algorithm is value < *j but the above
uses *j < value.  I don't think that the standard prevents an
implementation from using the compare object in the reverse direction.
There may be an "optimization".  Cover your six?

> As far as binary_search is concerned, well, I don't ever really need to use
> that, do I? lower_bound makes so much more sense...

Yes.  Binary_search has limited use.  However, equal_range could use
the algorithm rather than using lower_bound and upper_bound.  It would
also require both directions.

> > I don't think one of these can be generated by compose.
> 
> You mean a "GeneralCompare" object? Probably not ;)

Yes.

Later,
John