Re: [boost] Review: concept checks.

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2000-11-21 11:44:22

Ok, what we probably need is a several variants of LessThanComparable.
Here's the first two:

LessThanComparable<T>  (matches the standard)
  T a, b;
  a < b

Comparable<T> (matches SGI STL definition)
  T a, b;
  a < b
  a <= b
  a > b
  a >= b

The Comparable concept is certainly usefull for specifying things like
iterator concepts, etc. We just give it a name different from
LessThanComparable to prevent confusion and to respect the standard.

But there's another issue that relates to the sorting requirements. In
terms of comparison operators, what exactly does the standard require? I
think it is somewhat unclear. I don't think LessThanComparable matches the
intent of the standard (neither does Comparable) and we need another
concept.

lower_bound(ForIter first, ForIter last, T value)

The standard says T must be LessThanComparable. As I mentioned
before, this is somewhat irrelevant unless we also add the
requirement that iterator_traits<ForIter>::value_type is
the same type as T... but I don't think we want to add that.

Instead we need a LessThanComparable that works on two different types.
Something like:

LessThanComparable2<A,B>
  A a; B b;
  a < b

(I posted a concept like this a couple emails ago). However, this is also
not be enough. In section 25.3 we see several expressions that also need
to be valid:

  comp(x, x)  which implies a < a or b < b should be valid
  (b < a)   order of a and b can be flipped

Therefore, we end up with something more like this

LessThanComparable2<A,B>  (version 1)
  A is LessThanComparable
  B is LessThanComparable
  A a; B b;
  a < b
  b < a

I'm in favor of the above, though I could also see people arguing that if
"a < b" is a valid expression for the concept, then so should "b > a",
which would add the greater-than operator.

LessThanComparable2<A,B>  (version 2, with greater than)
  A is LessThanComparable
  B is LessThanComparable
  A a; B b;
  a < b
  b < a
  a > b
  b > a

Anyone agree/disagree? Preferences between version 1 and 2?

Also, we probably want a version of Comparable<T>, called
Comparable2<A,B> that defines all the operators between
types A and B.

Cheers,

Jeremy

On Tue, 21 Nov 2000, John Maddock wrote:

> Jeremy,
> 
> >Ahh, another place where the SGI STL docs differ from the standard.
> >Hmm, I'll have to change to match the standard... though I think
> >Matt's definition is better. Perhaps this is a candidate for a DR.
> 
> I don't think so, the sorting routines use a strict weak ordering:
> [ 25.3]
> "6 In the descriptions of the functions that deal with ordering relation-
>   ships we frequently use a notion of equivalence to  describe  concepts
>   such as stability.  The equivalence to which we refer is not necessar-
>   ily an operator==, but an equivalence relation induced by  the  strict
>   weak  ordering.   That is, two elements a and b are considered equiva-
>   lent if and only if !(a < b) && !(b < a)."
> 
> - John.

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