Re: [boost] Heterogeneous comparisons in binary search [was: A small holiday gift, I hope]

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2000-12-26 12:46:08

I like this formulation of the requirements... it is certainly much
simpler. I've also been thinking in this direction, but have a
couple worries:

One thing that concerns me is that as a result (I think) we get a
disconect between what it means for something to be sorted, and for
something to be binary-searchable.

To put it another way, we may need to have some notion to describe that a
range is in such a state so that the binary search will work for *any*
value object that is used with the comparison functor or operator <.
Normally, the definition of "sorted" ensures this. Related to this, I'm
worried that requirements based on a comparison "expression"  hide the
separation between the comparison function and the value object.

For a particular single call to binary search this may not be an issue,
but how would you specify the requirements for a sorted_vector class?

Cheers,
Jeremy

On Sun, 24 Dec 2000, David Abrahams wrote:
abraha> A small correction. I wrote:
abraha> 
abraha> > Add the following paragraph after 25.3 [lib.alg.sorting] paragraph 5:
abraha> > 
abraha> >   6 A sequence [begin, end) is partitioned with respect to an
abraha> > expression f(e) if   there exists a non-negative integer n such
abraha> > that for all  0 <= i < distance(begin, end), f(j) is true if and
abraha> > only if j < n.
abraha> 
abraha> Please imagine that I wrote the following instead:
abraha> 
abraha>   -6- A sequence [start, finish) is partitioned with respect to an
abraha>   expression f(e) if there exists a non-negative integer n such that
abraha>   for all 0 <= i < distance(start, finish), f(*(begin+i)) is true if
abraha>   and only if i < n.
abraha> 
abraha> Thanks,
abraha> Dave
abraha> 
abraha> 
abraha> 
abraha> 
abraha> 

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------