[boost] Re: shared_ptr: operator<

From: scleary_at_[hidden]
Date: 2000-02-28 10:28:36

joe gottman wrote: 
> Braden N. McDaniel wrote:
> > Kevlin Henney wrote:
> > > "For templates greater, less, greater_equal, and less_equal, the
> > > specializations for any pointer type yield a total order, even if
the
> > > built-in operators <, >, <=, >= do not." [20.3.3 para 8]
> >
> > Okay, silly question time: What exactly is meant here by the term
"total
> > order"?
> >
> 
>     An ordering relation such that for every pair of elements x and y,
> exactly one of the following statements is true: x < y, x == y, x > y.
> 

Sorry to be so nitpicky, but this isn't quite true.  The definition
above is for a strict weak ordering.  Total ordering implies that for
each different pair of elements: (x < y) || (x > y); it does _not_
allow them to be equal.  This means that x != y for all y.  Remember
that these restrictions are on the _values_ of the pointers, not the
pointers themselves; so two different values of pointers cannot ever
compare equal (of course), but two different pointers can compare equal
(if they have the same value).

This distinction between these relations is mainly important when you
are looking at the way STL's are implemented, or in some places in the
Standard (like [20.2/6]).  At first, what they do seems to be
unnecessarily complicated until you remember that what they're doing is
constructing a total ordering relation out of a strict weak ordering
relation, via [25.3/4].

In short:

Partial ordering (I don't think the definition for this appears in the
Standard, though the term is used):
  (x == x)
  either (x < y) or (x > y) or neither, but not both
  (x < y and y < z) implies (x < z)
Strict weak ordering [25.3/4]:
  (x == x)
  either (x < y) or (x > y) or neither, but not both
  (x < y and y < z) implies (x < z)
  (x == y and y == z) implies (x == z)
Total ordering:
  (x == x)
  either (x < y) or (x > y), but not both
  (x < y and y < z) implies (x < z)

Strict weak ordering = partial ordering + transitivity of equivalence
Total ordering = strict weak ordering without equivalent elements

        -Steve