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 ;)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk