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