# Boost :

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>
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: (219) 631-3906
----------------------------------------------------------------------