James Kuyper <kuyper@wizard.net> wrote in message
news:3904E0E6.BE552B31@wizard.net...
> Alex Oren wrote:
> >
> > On Sat, 4 Mar 2000 03:56:11 CST, James Kuyper <kuyper@wizard.net> wrote:
> >
> > } You should get a
> > } copy of the standard; you can get one online in PDF format for only
$18
> > } if you're a US citizen. I'm not sure what the price is in other
> > } countries.
> >
> > That is $18 from ansi.org regardless of your citizenship, you could be a
martian
> > for all they care.
>
> That was just a disclaimer, to cover my own uncertainty. A long time
> ago, when I first said that it cost only $18, I got a response from a
> non-US citizen complaining that it may only cost $18 here, but he
> couldn't order it at that price from his country, because the site
> wouldn't accept credit card orders from his country.

Well it worked for me (UK citizen, Visa Delta card).

J.G.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I (in Australia) ordered it online not long after it was available without
any problem. So I think you are right that might have to do with that
person's credit card company.

Don

James Kuyper <kuyper@wizard.net> wrote in message
news:3904E0E6.BE552B31@wizard.net...
> Alex Oren wrote:
> >
> > On Sat, 4 Mar 2000 03:56:11 CST, James Kuyper <kuyper@wizard.net> wrote:
> >
> > } You should get a
> > } copy of the standard; you can get one online in PDF format for only
$18
> > } if you're a US citizen. I'm not sure what the price is in other
> > } countries.
> >
> > That is $18 from ansi.org regardless of your citizenship, you could be a
martian
> > for all they care.
>
> That was just a disclaimer, to cover my own uncertainty. A long time
> ago, when I first said that it cost only $18, I got a response from a
> non-US citizen complaining that it may only cost $18 here, but he
> couldn't order it at that price from his country, because the site
> wouldn't accept credit card orders from his country. I don't know the
> details, and I've been unable to locate the relevant message using
> deja.news. It may have more to do with credit company policies than ANSI
> policies. The closest I could find was the following:
>
> Fergus Henderson, 1999-12-01:
> ....
> > It's now available from www.standards.com.au:
> > the price is AUD $437, which works out to be about USD $275.
>
> It would be hard to maintain so high a price, if the US site accepted
> orders from Australia. However, that's only circumstantial evidence.
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]
>


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 4 Mar 2000 03:56:11 CST, James Kuyper <kuyper@wizard.net> wrote:

} You should get a
} copy of the standard; you can get one online in PDF format for only $18
} if you're a US citizen. I'm not sure what the price is in other
} countries.

That is $18 from ansi.org regardless of your citizenship, you could be a martian
for all they care.


Have fun,
Alex.

--
My email address is intentionally mangled to foil spambots.
Please remove the "---filter---" from the address for replying.
Sorry for the inconvenience.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Alex Oren wrote:
>
> On Sat, 4 Mar 2000 03:56:11 CST, James Kuyper <kuyper@wizard.net> wrote:
>
> } You should get a
> } copy of the standard; you can get one online in PDF format for only $18
> } if you're a US citizen. I'm not sure what the price is in other
> } countries.
>
> That is $18 from ansi.org regardless of your citizenship, you could be a martian
> for all they care.

That was just a disclaimer, to cover my own uncertainty. A long time
ago, when I first said that it cost only $18, I got a response from a
non-US citizen complaining that it may only cost $18 here, but he
couldn't order it at that price from his country, because the site
wouldn't accept credit card orders from his country. I don't know the
details, and I've been unable to locate the relevant message using
deja.news. It may have more to do with credit company policies than ANSI
policies. The closest I could find was the following:

Fergus Henderson, 1999-12-01:
....
> It's now available from www.standards.com.au:
> the price is AUD $437, which works out to be about USD $275.

It would be hard to maintain so high a price, if the US site accepted
orders from Australia. However, that's only circumstantial evidence.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

rwhand@operamail.com wrote:
>
> >
> > They both say the same thing, assuming operator ==(T1 a, T1 b) is
> > equivalent to !(a<b)&&!(b <a).
> >
> > --
> > Pete Becker
> > Dinkumware, Ltd.
> > http://www.dinkumware.com
>
> Probably because my background is more mathematical than computer
> science, I have always been suspicious of defining operator ==(T,T) by !
> (a<b)&&!(b<a).  In my math books, I have never seen a partial ordering
> of a set by the operator <.  It is always by the operator <=.  I
> believe that the problem is that !(a<b || b<a) does not necessarily
> support transitivity.  Please consider the following program and its
> output.
....
> class A
>   {
>   private:
>     unsigned x;
>     unsigned y;
....
>     friend bool operator<(const A& a1, const A& a2)
>       {
>       return a1.x<a2.x && a1.y<a2.y;
>       }
....
>   };
....
> As you can see a simple class is defined that contains two members.  It
> would be a model for a uniform grid in the plane.  A comparison operator
> is defined as a friend.  An element is less than a second element iff
> both members of the first element are less than the respective members
> of the second element.
>
> The irreflexive property holds because a.x<a.x is false for all a.  The
> transitive property also holds since for any a, b and c, if a.x<b.x
> and b.x<c.x, then a.x<c.x.  A similar line can be written for the y
> component.  So if a<b and b<c, then a<c.  Therefore, the operator < in
> the above program does fit the definition in Matthew Austern's book.

The standard requires that any comparison operator used in various
contexts must induce a strict weak ordering. Using equiv(a,b) as
shorthand for (!comp(a,b)&&!comp(b,a)), this means among other things
that equiv(a,b) && equiv(b,c) must imply equiv(a,c). Your example
operator<() doesn't qualify, which is essentially what your example
program shows.

This has nothing to do with the use of '<' vs. '<='. Whether or not a
'==' defined in terms of a comparison operator is transitive depends
upon the properties of that comparison operator, no matter which
operator it is. If you defined 'a==b' as  'a<=b && b<=a', you could get
exactly the same problems you describe, by defining 'operator<=()' as
'a1.x<=a2.x || a1.y<=a2.y)'.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Dear James,

Thanks for replying.  I am not in total disagreement with your points, but I
see them from a different point of view.  Please see below:

>>  Therefore, the operator < in
> > the above program does fit the definition in Matthew Austern's book.
>
> The standard requires that any comparison operator used in various
> contexts must induce a strict weak ordering. Using equiv(a,b) as
> shorthand for (!comp(a,b)&&!comp(b,a)), this means among other things
> that equiv(a,b) && equiv(b,c) must imply equiv(a,c). Your example
> operator<() doesn't qualify, which is essentially what your example
> program shows.

I agree that the standard requires the equivalence operator to be
transitive.  But why force a particular definition for operator ==() from
operator <()?  The issue is whether some operator ==() fits the axioms of an
equivalance relationship and whether its operator <() fits the axioms of
irreflexivity and transitivity.  So my issue is not with your interpretation
but with the standard itself.

To belabor this point a little, what on earth does it mean to define "weak"
as not as "strong" as a total ordering but "stronger" than a partial
ordering? (p. 554 of the standard)  What does strong mean here?

I have searched the ISO document for a definition of total ordering.
Perhaps you have a different definition than me.  I have always seen the
definition that a set is totally ordered by its partial order <=, if for all
a and b in the set, that either a<=b or b<=a.  In other words, every pair of
elements of the set are comparable.  If that requirement breaks down, then
the set is only partially ordered.  It seems total and partial are the only
two options from that definition.  Does the standard have another
definition?

On the other hand, there is a practical programming issue here as well.
Many programmers will lack your incisive understanding of the standard and
toss together any old operator <() and then go on to define operator ==() as
(!comp(a,b)&&!comp(b,a)).  As I pointed out in my example, that might lead
to catastrophe.  I suspect that they might forget that the operator ==()
must be transitive.


>
> This has nothing to do with the use of '<' vs. '<='. Whether or not a
> '==' defined in terms of a comparison operator is transitive depends
> upon the properties of that comparison operator, no matter which
> operator it is. If you defined 'a==b' as  'a<=b && b<=a', you could get
> exactly the same problems you describe, by defining 'operator<=()' as
> 'a1.x<=a2.x || a1.y<=a2.y)'.
>

My point was that '==' has to be independently defined from '<'.  Why else
does the standard require the additional requirement that '==' be
transitive.  How is it that many operator ==()'s are consistent with the
same operator <()?  In my example, using the '==' that equates the x values
finds that c1=b1.  But the '==' that equates the y values finds that c1!=c2
(not shown before).  Both relationships will partially order the set of
class A.  The order will be different.  Therefore, there is no function that
will generate the unique and only equivalence relationship from  '<'.

On the other hand defining a==b as a<=b and b<=a will not be a problem since
it is used in myriad math books.  <= must, of course, fulfill the axioms of
partial ordering.  In particular it must be reflexive (x<=x), antisymmetric
(x<=y && y<=x implies x==y), and transitive.

Defining operator <=() as the independent relationship localizes all the
decisions about ordering in one function body.  As long as it fulfills the
three axioms of a partial ordering, all the other relationships can be
defined as templates without further worry.  The code should be easier to
maintain.  Obviously, the standards committee did not do it this way.

I guess I have gone on long enough.  Enjoyed your response.  Thanks.

Best wishes,

Bob Hand


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Robert W. Hand" wrote:
....
> I have searched the ISO document for a definition of total ordering.

There doesn't seem to be one, which means that you should follow the
standard mathematical definition.

> Perhaps you have a different definition than me.  I have always seen the
> definition that a set is totally ordered by its partial order <=, if for all
> a and b in the set, that either a<=b or b<=a.  In other words, every pair of
> elements of the set are comparable.  If that requirement breaks down, then
> the set is only partially ordered.  It seems total and partial are the only
> two options from that definition.  Does the standard have another
> definition?

Yes - see section 25.3 p4.
A strict weak ordering induces an equivalence relation defined by
"!comp(a,b)&&!comp(b,a)", and must provide a total ordering of the
equivalence classes of that relation. Both the comparison and the
induced equivalence relation must be transitive. Your example doesn't do
that. In order for it to qualify as a total ordering, each of the
equivalence classes would have to have only one element.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Robert W. Hand" wrote:
>
> Dear James,
>
> Thanks for replying.  I am not in total disagreement with your points, but I
> see them from a different point of view.  Please see below:
>
> >>  Therefore, the operator < in
> > > the above program does fit the definition in Matthew Austern's book.
> >
> > The standard requires that any comparison operator used in various
> > contexts must induce a strict weak ordering. Using equiv(a,b) as
> > shorthand for (!comp(a,b)&&!comp(b,a)), this means among other things
> > that equiv(a,b) && equiv(b,c) must imply equiv(a,c). Your example
> > operator<() doesn't qualify, which is essentially what your example
> > program shows.
>
> I agree that the standard requires the equivalence operator to be
> transitive.  But why force a particular definition for operator ==() from
> operator <()?  The issue is whether some operator ==() fits the axioms of an
> equivalance relationship and whether its operator <() fits the axioms of
> irreflexivity and transitivity.  So my issue is not with your interpretation
> but with the standard itself.
>
> To belabor this point a little, what on earth does it mean to define "weak"
> as not as "strong" as a total ordering but "stronger" than a partial
> ordering? (p. 554 of the standard)  What does strong mean here?

An example of a strict weak order that is not a total order
would be
a before b <=> |a|<|b|

This doesn't give you a total order, since neither -3 before 3,
or 3 before -3, but it gives you an equivalence relation
(not a before b and not b before a <=> |a| == |b|), and it
induces a total order on the equivalence classes of that
induced equivalence relation.

That is, you have unordered subsets, but a total order between
those subsets, f.ex. with the above "before" relation,

{0} before {1, -1} before {2, -2} before {3, -3} before ...

but no relative order between a and -a.

[...]

> My point was that '==' has to be independently defined from '<'.  Why else
> does the standard require the additional requirement that '==' be
> transitive.  How is it that many operator ==()'s are consistent with the
> same operator <()?

Possibly because most often the chosen strict weak order is indeed
a total order?

A good example of an application of a strict weak order would be
a phone book. Of course, you want the names to be alphabetically
sorted; this implies an order for the phone book entries.
However, if someone has two phone numbers, the order in
which those two entries appear in the phone book doesn't matter.
Therefore sorting alphabetically doesn't give a total order for
phone book entries. It does, however, gives atrict weak order
(if phone numbers belong to different persons, you can tell
which one comes first), with the induced equivalence relation
"belongs to the same person".

However, if you'd compare two phone book entries, you'd
consider them equal if and only if both the name and the
phone number are equal.

>  In my example, using the '==' that equates the x values
> finds that c1=b1.  But the '==' that equates the y values finds that c1!=c2
> (not shown before).  Both relationships will partially order the set of
> class A.  The order will be different.  Therefore, there is no function that
> will generate the unique and only equivalence relationship from  '<'.

That's because you didn't provide a strict weak order.

>
> On the other hand defining a==b as a<=b and b<=a will not be a problem since
> it is used in myriad math books.

Defining over the properties of "a<=b" is defining over the
properties of "not a>b", since both are equivalent. But then,
this definition is actually a definition over the properties
of "a>b", since "not a>b" is just the negation of that.
And thus, it's equivalent to a definition over the properties
of "b<a", since that's again just the same.
Especially "a<=b and b<=a" is totally equivalent to
"not b<a and not a<b".

>  <= must, of course, fulfill the axioms of
> partial ordering. In particular it must be reflexive (x<=x), antisymmetric
> (x<=y && y<=x implies x==y), and transitive.

The second one is a triviality if "==" is defined as above.
Thus, to prove that "==" as defined above is an equivalence
relation, we are left with reflexive and transitive.
Indeed, every definition that uses "==" (or "!=") is flawed,
if "==" shall be defined from the here defined relationship.
And since all statements about "<=" are at the same time
statements about ">", and therefore statements about "<",
a definition through "<=" cannot provide anything that
a definition over "<" can't.

After all, "a<=b" and "not b<a" are just two ways to say
the same thing.

>
> Defining operator <=() as the independent relationship localizes all the
> decisions about ordering in one function body.

So does defining operator<.

>  As long as it fulfills the
> three axioms of a partial ordering, all the other relationships can be
> defined as templates without further worry.

Wrong. No matter if you use "<" or "<=" as the "fundamental"
operator, you always need a strict weak order to get an
equivalence relation.

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Barry Margolin <barmar@bbnplanet.com> writes:

|>  >This is also the official reason.  I find it a debatable reason, since
|>  >in many cases, == can be implemented much cheaper than <.  And I can
|>  >hardly think of a type where < would make sense, but == wouldn't.

|>  Since the type already has to provide <, this definition reduces the
|>  requirements of the type to the minimal absolutely required.

But this begs the question: STL is not the only user of the class
(presumably) -- if == is reasonable, the class authors should provide
it, STL or no.  And I can't think of any class where < would be
reasonable, and == not.

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh   ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>
> They both say the same thing, assuming operator ==(T1 a, T1 b) is
> equivalent to !(a<b)&&!(b <a).
>
> --
> Pete Becker
> Dinkumware, Ltd.
> http://www.dinkumware.com

Probably because my background is more mathematical than computer
science, I have always been suspicious of defining operator ==(T,T) by !
(a<b)&&!(b<a).  In my math books, I have never seen a partial ordering
of a set by the operator <.  It is always by the operator <=.  I
believe that the problem is that !(a<b || b<a) does not necessarily
support transitivity.  Please consider the following program and its
output.

Run of program:
b1 is less than b2
c1 is less than c2
b1 is equal to c1
b1 is not equal to b2
b2 is not less than c2
c1 is not less than b2
b2 is not less than c1
c1 is equal to b2
Press enter to continue...

Program listing:
#include <iostream>

class A
  {
  private:
    unsigned x;
    unsigned y;
  public:
    A(void): x(0), y(0)
      {
      }
    A(unsigned x1, unsigned y1): x(x1), y(y1)
      {
      }
    ~A(void)
      {
      }
    friend bool operator<(const A& a1, const A& a2)
      {
      return a1.x<a2.x && a1.y<a2.y;
      }
    friend bool operator==(const A& a1, const A& a2)
      {
      return !((a1<a2) || (a2<a1));
      }
  };

int main(void)
  {
  A b1(1, 4);
  A b2(3, 8);
  A c1(1, 12);
  A c2(2, 16);
  using std::cout;
  using std::endl;
  using std::cin;
  if(b1<b2)
    cout<<"b1 is less than b2"<<endl;
  else
    cout<<"b1 is not less than b2"<<endl;
  if(c1<c2)
    cout<<"c1 is less than c2"<<endl;
  else
    cout<<"c1 is not less than c2"<<endl;
  if(b1==c1)
    cout<<"b1 is equal to c1"<<endl;
  else
    cout<<"b1 is not equal to c1"<<endl;
  if(b1==b2)
    cout<<"b1 is equal to b2"<<endl;
  else
    cout<<"b1 is not equal to b2"<<endl;
  if(b2<c2)
    cout<<"b2 is less than c2"<<endl;
  else
    cout<<"b2 is not less than c2"<<endl;
  if(c1<b2)
    cout<<"c1 is less than b2"<<endl;
  else
    cout<<"c1 is not less than b2"<<endl;
  if(b2<c1)
    cout<<"b2 is less than c1"<<endl;
  else
    cout<<"b2 is not less than c1"<<endl;
  if(c1==b2)
    cout<<"c1 is equal to b2"<<endl;
  else
    cout<<"c1 is not equal to b2"<<endl;

  char buf[5];
  cout<<"Press enter to continue...";
  cin.getline(buf, 1);
  return 0;
  }

As you can see a simple class is defined that contains two members.  It
would be a model for a uniform grid in the plane.  A comparison operator
is defined as a friend.  An element is less than a second element iff
both members of the first element are less than the respective members
of the second element.

The irreflexive property holds because a.x<a.x is false for all a.  The
transitive property also holds since for any a, b and c, if a.x<b.x
and b.x<c.x, then a.x<c.x.  A similar line can be written for the y
component.  So if a<b and b<c, then a<c.  Therefore, the operator < in
the above program does fit the definition in Matthew Austern's book.

The equivalence operator== is defined as !(a<b || b<a) for objects a
and b.  But look what happens.

Using that definition leads to a contradiction.  The output shows that

c1==b2 and b1==c1.

So b1 must equal b2, but b1 is less than b2.  We have reached a
contradiction.

So a less than cannot imply an equivalence relationship.  To repair the
code, an independent definition of operator== must be given.  Here are
three examples that would work:

1)  Two objects are equal if the x members are equal.
2)  Two objects are equal if the y members are equal.
3)  Two objects are equal if both the x and y members are equal.

Using the first definition, the friend function is now:

friend bool operator==(const A& a1, const A& a2)
  {
  return a1.x==a2.x;
  }

and the run is now:

b1 is less than b2
c1 is less than c2
b1 is equal to c1
b1 is not equal to b2
b2 is not less than c2
c1 is not less than b2
b2 is not less than c1
c1 is not equal to b2
Press enter to continue...

The equivalence classes are now lines running vertically on the grid.
The definition does separate the grid into clear cut equivalence
classes, and c1 is no longer equal to b2.  So the contradiction is now
gone.

It should be noted that not all objects can be compared.  c1 and b2 are
not comparable.  But the computer will make them equal if an independent
equivalence relationship is not defined.

So I think that we need to be very careful about defining everything
from operator <.


Best wishes,

Bob Hand


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Dear James,

Thanks for helping me understand this issue.  I believe that I now
understand what the committee has done.  It is actually very smart, perhaps
brilliant.  But the definitions and purpose do diverge somewhat from the
usual mathematical development, leading to my bewilderment.  Please see
below.

> > I have searched the ISO document for a definition of total ordering.
>
> There doesn't seem to be one, which means that you should follow the
> standard mathematical definition.

A very kind correspondent sent me a web site from sgi that defines it.  It
is different than the definition that I have used in the past.  Please see

http://www.sgi.com/Technology/STL/LessThanComparable.html .

The development that I suggested in my previous posts is that of the
standard partial ordering of a set.  That means that every member may not be
comparable to every other member.  So there may be two members, a and b, of
a partially ordered set so that a<b, a>b, and a==b are all false.  I am
happy with that idea.  My example, corrected with a proper equivalence
relationship such as I did in my first post, is a partially ordered set.  In
particular, c1 and b2 are not comparable.

Mathematicians define a chain to be a subset of a partially ordered set in
which all members of the subset are comparable, i.e. for all a and b in the
chain, either a<=b or b<=a (or both).  So in my example, the set was not a
chain.  Several terms exist to describe a partially ordered set that is a
chain.  I have seen both totally ordered and linear.  sgi does not use that
definition for totally ordered so I shall not in the following.

The kindly correspondent also pointed out that the practical use of ordering
is in sorting.  Of course, it would be difficult to sort a partially ordered
set that is not a chain.  No matter where the sort algorithm started, it
could not reach all the elements of the set by iterating along the less than
operator.

So it becomes necessary to find a particular ordering relationship that is n
ot only a partial order, but that also reduces the set to a chain.  Then the
algorithm can start at the beginning and work to the end.

Now there are some issues whether the set is "well-ordered" (all subsets
contain a minimal element), but I suspect that computer chains will be
well-ordered since they are inherently finite.  One theorem from set theory
states: "A linear order X is well-ordered iff there is no infinite
descending chain of elements of X".  It seems hard to have a computer have
an infinite descending chain. So in principle, it seems reasonable to reduce
ordering to that of finding a less than relationship that reduces the set of
objects to a chain.

Of all the operator <()'s that provide irreflexivity (x<x is false) and
transitivity (x<y and y<z implies x<z),  many will not make a set into a
chain.  My example did not by design.  But the committee's selection does
seem to work.  The only admissible < relationship is one that insists that
all elements of the set are comparable.  If a<b and b<a are both false, then
another relationship '==' (!(a<b ||b<a)) will be true.  And that
relationship must be an equivalence relationship.  The axioms of reflexivity
(x==x) and symmetry (x==y and y==x) are easily seen to be true.  But
transitivity does not follow, so it must be demanded in the definition as
they have done.  That relationship (both < and ==) is given the name of a
strict weak ordering.

Now, it is possible to start at the beginning and work to the end of the
set.  But the equivalence class partition that is induced may allow several
members of the set to belong to the same equivalence class.  sgi defines a
total order to be such a partition that allows only a single element per
class.

So I now understand what the committee did.  Their order allows reduction of
the set to a chain.  It may be that some developers may want to use a
partial order for reasons other than sorting.  It is not clear how the
standard might be enforced by future compilers.  I hope that a compiler
error will not be emitted if operator <() and operator ==() are defined as I
did in my earlier example.

Thanks for your time and patience.

Best wishes,

Bob Hand


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Robert W. Hand" wrote:
>
> Dear James,
....
> > > I have searched the ISO document for a definition of total ordering.
> >
> > There doesn't seem to be one, which means that you should follow the
> > standard mathematical definition.
>
> A very kind correspondent sent me a web site from sgi that defines it.  It
> is different than the definition that I have used in the past.  Please see
>
> http://www.sgi.com/Technology/STL/LessThanComparable.html .

That definition references their definition of "strict weak ordering",
which is the same as the definition in the standard. You should get a
copy of the standard; you can get one online in PDF format for only $18
if you're a US citizen. I'm not sure what the price is in other
countries.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

jpotter@falcon.lhup.edu (John Potter) writes:

|>  Maybe < is defined and == is not?

Or maybe == is significantly cheaper than <?

Can you give me an example of a correctly designed class where < is
defined and == isn't?

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orientie objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Sjoerd Schreuder <sjoerd@geodan.nl> writes:

|>  I don't know about the official reason, but your version uses
|>  both operator< and operator==, while the official version only
|>  uses operator<. Because they both provide a proper ordening, the
|>  official version is "better" because it depends on only one function
|>  (in stead of two).

This is also the official reason.  I find it a debatable reason, since
in many cases, == can be implemented much cheaper than <.  And I can
hardly think of a type where < would make sense, but == wouldn't.

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orientie objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

kanze@gabi-soft.de wrote:
>
> Sjoerd Schreuder <sjoerd@geodan.nl> writes:
>
> |>  I don't know about the official reason, but your version uses
> |>  both operator< and operator==, while the official version only
> |>  uses operator<. Because they both provide a proper ordening, the
> |>  official version is "better" because it depends on only one function
> |>  (in stead of two).
>
> This is also the official reason.  I find it a debatable reason, since
> in many cases, == can be implemented much cheaper than <.  And I can
> hardly think of a type where < would make sense, but == wouldn't.

There's a consistency issue involved. If you implement only one
comparison function directly, and let the others be defined in terms of
it, then you reduce the likelihood of defining them inconsistently. You
can implement all of the comparison operators by using any one of '<',
'>', '<=' or '>=', but you can't implement any of the those by using
'==' or '!='. The standard chose '<', which is at least as good as any
of the other three.
I wish std::rel_ops<> were less clumsy to use.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <861z686gv6.fsf@gabi-soft.de>,  <kanze@gabi-soft.de> wrote:
>Sjoerd Schreuder <sjoerd@geodan.nl> writes:
>
>|>  I don't know about the official reason, but your version uses
>|>  both operator< and operator==, while the official version only
>|>  uses operator<. Because they both provide a proper ordening, the
>|>  official version is "better" because it depends on only one function
>|>  (in stead of two).
>
>This is also the official reason.  I find it a debatable reason, since
>in many cases, == can be implemented much cheaper than <.  And I can
>hardly think of a type where < would make sense, but == wouldn't.

Since the type already has to provide <, this definition reduces the
requirements of the type to the minimal absolutely required.

--
Barry Margolin, barmar@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Tue, 22 Feb 2000 07:58:03 CST, kanze@gabi-soft.de wrote:

: jpotter@falcon.lhup.edu (John Potter) writes:
:
: |>  Maybe < is defined and == is not?
:
: Or maybe == is significantly cheaper than <?

That discussion went around a while ago.  No arguement.

: Can you give me an example of a correctly designed class where < is
: defined and == isn't?

No.  I can still appreciate the beauty of defining < for pair in terms
of nothing other than < for the elements.  I would be very surprised to
find == for pair defined in terms of < rather than == for the elements.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Seth Jones wrote:
>
> In article <darin-45D323.09292610022000@fullnews.metawire.com>,
> darin@bentspoon.com says...
> > In article <38A251BF.A74EE276@multinet.com.au>, Michael Slade
> > <michael.slade@multinet.com.au> wrote:
> >
> > > I was looking through a C++ reference and noticed some wierdness.  I
> > > checked the egcs headers to see if the same wierdness was there, and
> > > sure enough:
> > >
> > > template <class T1, class T2>
> > > inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
> > >   return x.first < y.first || (!(y.first < x.first) && x.second <
> > > y.second);
> > > }
> > >
> > > Now, is it just the wrong time of day for me, or does that not provide a
> > > proper ordering?  shouldn't it be:
> > >
> > > return x.first < y.first || (y.first == x.first && x.second < y.second);
> > >
> > > ?  Or is there a reason why it's that way?
> >
> > Your suggested implementation gives the same result as the standard's
> > implementation, except that it requires the type of "first" to implement
> > an == operator. The pair < operator is based only on the underlying <
> > operator, so it can work even with classes that don't define ==
> > operators.
> >
> > Note that once you know that !(x.first < y.first), because of the check
> > before the "||", and that !(y.first < x.first), because of the check
> > before the "&&", you know that x.first is the same as y.first, so you
> > don't need to use == to establish that.
> >
>
> Strictly speaking, this is only true if T1::operator< is a total order on
> T1. The standard library seems to make this assumption consistently.
> Hopefully the standard states this explicitely somewhere.

It gives a total order if both T1::operator< and T2::operator<
provide a total order.
It also gives a strict weak order, if both T1 and T2 provide
a strict weak order.

The STL generally assumes a strict weak order.

BTW, is there a reason why pair has no order parameters, like

template<class T1, class T2,
         class Order1 = less<T1>,
         class Order2 = less<T2> >
 class pair;

?

Note that this is not allowed even as extension, since the
following program will behave differently:

#include <cassert>
#include <utility>
#include <functional>

class X
{
public:
  X(i): value(i) {}
  operator int() { return value; }
  bool operator<(X const& other) const { return value<other.value; }
private:
  int value;
};

template<> struct std::less<X>
{
  bool operator()(X const& x1, X const& x2)
  {
    return x2 < x1; // yes, that's perverse ;-)
  }
};

int main()
{
  assert(std::pair<X, X>(X(2), X(3)) < std::pair<X, X>(X(4), X(5)));
}

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I was looking through a C++ reference and noticed some wierdness.  I
checked the egcs headers to see if the same wierdness was there, and
sure enough:

template <class T1, class T2>
inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
  return x.first < y.first || (!(y.first < x.first) && x.second <
y.second);
}

Now, is it just the wrong time of day for me, or does that not provide a
proper ordering?  shouldn't it be:

return x.first < y.first || (y.first == x.first && x.second < y.second);

?  Or is there a reason why it's that way?

Mick.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

From: Michael Slade <michael.slade@multinet.com.au

> I was looking through a C++ reference and noticed some wierdness.  I
> checked the egcs headers to see if the same wierdness was there, and
> sure enough:
>
> template <class T1, class T2>
> inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y)

>   return x.first < y.first || (!(y.first < x.first) && x.second <
> y.second);
> }
>
> Now, is it just the wrong time of day for me, or does that not provide a
> proper ordering?  shouldn't it be:
>
> return x.first < y.first || (y.first == x.first && x.second < y.second);

Expand the first one

( a < b ) ||  ( !( b < a )  && ( c < d ) )
is
true if a < b
otherwise, b <= a, so if  !(b<a), then b==a,
So the whole thing is
if a!=b
    return a < b
else
    return ( c < d )

So its equivalent.

> ?  Or is there a reason why it's that way?

Yes - it means that you can just write operator< and don't need operator==,
or any other comparison operator. The whole stl just assumes < exists.

Ric






---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <38A251BF.A74EE276@multinet.com.au>, Michael Slade
<michael.slade@multinet.com.au> wrote:

> I was looking through a C++ reference and noticed some wierdness.  I
> checked the egcs headers to see if the same wierdness was there, and
> sure enough:
>
> template <class T1, class T2>
> inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
>   return x.first < y.first || (!(y.first < x.first) && x.second <
> y.second);
> }
>
> Now, is it just the wrong time of day for me, or does that not provide a
> proper ordering?  shouldn't it be:
>
> return x.first < y.first || (y.first == x.first && x.second < y.second);
>
> ?  Or is there a reason why it's that way?

Your suggested implementation gives the same result as the standard's
implementation, except that it requires the type of "first" to implement
an == operator. The pair < operator is based only on the underlying <
operator, so it can work even with classes that don't define ==
operators.

Note that once you know that !(x.first < y.first), because of the check
before the "||", and that !(y.first < x.first), because of the check
before the "&&", you know that x.first is the same as y.first, so you
don't need to use == to establish that.

Any standard library implementation is full of code that uses < to
establish a complete ordering and avoids use of == in this manner.

    -- Darin

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michael Slade wrote:
>
> I was looking through a C++ reference and noticed some wierdness.  I
> checked the egcs headers to see if the same wierdness was there, and
> sure enough:
>
> template <class T1, class T2>
> inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
>   return x.first < y.first || (!(y.first < x.first) && x.second <
> y.second);
> }
>
> Now, is it just the wrong time of day for me, or does that not provide a
> proper ordering?  shouldn't it be:
>
> return x.first < y.first || (y.first == x.first && x.second < y.second);

Rewrite to: (reverse x.f < y.f to y.f > x.f and add it to the right side)
  return x.f < y.f || ((y.f > x.f || y.f == x.f) && x.s < y.s);
rewrite to:
  return x.f < y.f || (y.f >= x.f && x.s < y.s);
rewrite to:
  return x.f < y.f || (!(y.f < x.f) && x.s < y.s);

They are equivalent: when one is true, the other is true as well,
and when one is false, the other is false as well.

> ?  Or is there a reason why it's that way?

I don't know about the official reason, but your version uses
both operator< and operator==, while the official version only
uses operator<. Because they both provide a proper ordening, the
official version is "better" because it depends on only one function
(in stead of two).

Sjoerd Schreuder

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michael Slade wrote:
>
> I was looking through a C++ reference and noticed some wierdness.  I
> checked the egcs headers to see if the same wierdness was there, and
> sure enough:
>
> template <class T1, class T2>
> inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
>   return x.first < y.first || (!(y.first < x.first) && x.second <
> y.second);
> }
>
> Now, is it just the wrong time of day for me, or does that not provide a
> proper ordering?  shouldn't it be:
>
> return x.first < y.first || (y.first == x.first && x.second < y.second);
>

They both say the same thing, assuming operator ==(T1 a, T1 b) is
equivalent to !(a<b)&&!(b <a).

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michael Slade wrote in message <38A251BF.A74EE276@multinet.com.au>...

>?  Or is there a reason why it's that way?

Probably a reason it is that way. Operator < may be the only comparison
operator and operator == many not be defined.

Stephen Howe


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <darin-45D323.09292610022000@fullnews.metawire.com>,
darin@bentspoon.com says...
> In article <38A251BF.A74EE276@multinet.com.au>, Michael Slade
> <michael.slade@multinet.com.au> wrote:
>
> > I was looking through a C++ reference and noticed some wierdness.  I
> > checked the egcs headers to see if the same wierdness was there, and
> > sure enough:
> >
> > template <class T1, class T2>
> > inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
> >   return x.first < y.first || (!(y.first < x.first) && x.second <
> > y.second);
> > }
> >
> > Now, is it just the wrong time of day for me, or does that not provide a
> > proper ordering?  shouldn't it be:
> >
> > return x.first < y.first || (y.first == x.first && x.second < y.second);
> >
> > ?  Or is there a reason why it's that way?
>
> Your suggested implementation gives the same result as the standard's
> implementation, except that it requires the type of "first" to implement
> an == operator. The pair < operator is based only on the underlying <
> operator, so it can work even with classes that don't define ==
> operators.
>
> Note that once you know that !(x.first < y.first), because of the check
> before the "||", and that !(y.first < x.first), because of the check
> before the "&&", you know that x.first is the same as y.first, so you
> don't need to use == to establish that.
>

Strictly speaking, this is only true if T1::operator< is a total order on
T1. The standard library seems to make this assumption consistently.
Hopefully the standard states this explicitely somewhere.

Seth Jones

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Fri, 11 Feb 2000 03:47:31 CST, Michael Slade
<michael.slade@multinet.com.au> wrote:

: I was looking through a C++ reference and noticed some wierdness.  I
: checked the egcs headers to see if the same wierdness was there, and
: sure enough:
:
: template <class T1, class T2>
: inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
:   return x.first < y.first || (!(y.first < x.first) && x.second <
: y.second);
: }
:
: Now, is it just the wrong time of day for me, or does that not provide a
: proper ordering?  shouldn't it be:
:
: return x.first < y.first || (y.first == x.first && x.second < y.second);
:
: ?  Or is there a reason why it's that way?

Maybe < is defined and == is not?

  x.first < y.first
  ||  // got here; so, either x.first == y.first or y.first < x.first
  (
  ! (y.first < x.first)  // means they must be equal

You deserve a nap ;)
John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Seth Jones wrote:
>
> In article <darin-45D323.09292610022000@fullnews.metawire.com>,
> darin@bentspoon.com says...
....
> > Note that once you know that !(x.first < y.first), because of the check
> > before the "||", and that !(y.first < x.first), because of the check
> > before the "&&", you know that x.first is the same as y.first, so you
> > don't need to use == to establish that.
> >
>
> Strictly speaking, this is only true if T1::operator< is a total order on
> T1. The standard library seems to make this assumption consistently.
> Hopefully the standard states this explicitely somewhere.

Yes, it does, but only in certain contexts.

23.1: If c1 and c2 are both the same type of container, with a value
type of T, use of c1<c2 requires that "< is defined for values of T, <
is a total ordering relation."

24.1: For random access iterators, < and > are required to define
(oppositely oriented) total ordering relationships.

More often it requires only strict weak ordering, which is defined in
section 25.3, and section 20.1.2 p1 defines that a given type is
LessThanComparable if a<b defines "a strict weak ordering relation". The
standard requires the following types must be LessThanComparable:

20.2.1: The types for which the templated std::operator!=, >, <= and >=
are instantiated.

25.3.3: The types for which the Binary search algorithms are
instantiated.
25.3.7: The types for which std::min<>() or std::max<>() are
instantiated.]

For each of the algorithms in Section 25.3 that take a Compare template
argument, "comp(*i, *j)!=false", is said to default to "*i < *j !=
false" for the versions that don't take the Compare argument.  They're
required to induce a strict weak ordering relationship on the values.

23.1.2: "Each associative container is parameterized on a Key and an
ordering relation Compare that induces a strict weak ordering (25.3) on
elements of Key."
Therefore, anytime that the Compare object is less<Key> (which is the
default Compare object for all of the standard-defined associative
containers), then the Key type must be LessThanComparable.

23.2.2.4: std::list<T>::merge<Compare>() and std::list<T>::sort<Compare>
require that the compare object define a strict weak ordering; thus, if
it's std::less<T>, which is effectively the default compare object, then
T must be LessThanComparable.

23.2.3.2: std::priority_queue<T,Container,Compare> is said to assume
that Compare defines a strict weak ordering on Container::value_type,
and defaults to std::less<Container::value_type>.
This peculiarly weak wording doesn't actually say that Compare is
required to define such an ordering, but in practice I wouldn't
recommend using one that didn't.

If none of these sections apply, '<' is pretty much unconstrained for
user-defined types.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]