Re: [boost] Review: concept checks.

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-11-25 19:47:53

On Sat, 25 Nov 2000, Jeremy Siek wrote:

> Well, if we really want to minimize the requirements for lower_bound
> (which I agree in general is a very good idea) then we have to define
> strict weak ordering in a much different way, or not require strict weak
> ordering for lower_bound() and require something else.
> 
> The definition of strict weak ordering in 25.3 makes lots of uses of T < T
> and value_type < value_type.

Yes, and it makes sense for sorting, but maybe not for searching.

> So does anyone know how to either:
> 
> 1) create an alternate definition of strict weak ordering
>  that only uses value_type < T.

The definition is used to define the order which the range must
satisfy.  Value_type < value_type is required for that.  The
assumption for the binary search algorithms is that the range
is ordered.  I don't think that anyone wants a run time verification
of that order every time that lower_bound is called.  If not, there
is no need for value_type < value_type in lower_bound.

> 2) create some alternate requirement (not strict weak ordering)
>   that is enough to ensure lower_bound() will work.

The requirement is there, I just don't think that it is testable.

> I'm no expert on sorting, so I don't know if 1) or 2) is possible,
> or what form they would take.

Maybe I just don't understand the problem.  How about an example?

struct S { int a; int b; };
struct LessS { bool operator() (S const& lhs, S const& rhs) {
      return lhs.a < rhs.a; };
struct FinderS { bool operator() (S const& lhs, int rhs) {
      return lhs.a < rhs; };

vector S v;
// fill v
sort(v.begin(), v.end(), LessS());
cout << lower_bound(v.begin(), v.end(), 42, FinderS())->b;

This will work on all implementations which I have seen.  Note also
that operator< could have been defined and used for either or both.
The point is that the operator used for lower_bound need not be the
same operator that was used for sort.  If I were to compile this
with some strange library which used other operations, I would
get a compile error.  If I compile it with a reasonable library
which only uses the needed and supplied operator, I would not
like to see some silly concept violation error.

If I replace < with > in FinderS, the algorithm will not work
and no concept check can detect it.  I guess that I just don't
see the point.  The testable requirements are the operations
that the algorithm uses.  The compiler checks them.

John