Partial vs. strict weak ordering (was Re: [PATCH] Postinstall script ordering in setup - take 3)

[Igor Pechtchanski]

Rob,

On 17 Mar 2003, Robert Collins wrote:

> On Mon, 2003-03-17 at 06:51, Igor Pechtchanski wrote:
>
> > STL containers won't choke, as they only need a partial order, AFAIU.
> > The "fail" simply means it's not a strict weak ordering.
>
> They can and will do the wrong thing.

You're right, of course.  My statement above was too general.  Let me try
again:

STL containers that require LessThanComparable (i.e., partial ordering)
will not choke.  Sorted Associative Containers that require
StrictWeakOrdering *will* fail (because the relation I defined isn't).

I thought that only LessThanComparable is needed for the "sort()" function
of the list container.  Upon rereading
<http://www.sgi.com/tech/stl/List.html>, however, I realized that the
sort() function does require a strict weak ordering (but doesn't refer to
StrictWeakOrdering, but rather to LessThanComparable).
I'm a bit confused now.

> because it's not a strict weak ordering, if we have:
> [snip]
> This is because your ordering requires direct comparison to all members
>
> I don't have time right now to go into the maths above, will do so
> later.
>
> Rob

I believe I agreed before that the operator I defined is not a strict weak
ordering.  Now it seems that that's what's needed, even for the list's
sort().  I'll need to think on that one some more.
	Igor
P.S. FYI, sort() called with my operator< seems to do the right thing,
surprisingly, producing a topologically-ordered list...  Go figure...
-- 
				http://cs.nyu.edu/~pechtcha/
      |\      _,,,---,,_		pechtcha@cs.nyu.edu
ZZZzz /,`.-'`'    -.  ;-;;,_		igor@watson.ibm.com
     |,4-  ) )-,_. ,\ (  `'-'		Igor Pechtchanski
    '---''(_/--'  `-'\_) fL	a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune