On to Hydro

Tyler Close tjclose@yahoo.com
Thu, 17 Aug 2000 09:35:53 -0400


Me (Tyler) responding to Markm:
> > Another is "<" for strict subset.
>
> Could you explain this more.

Doh. Nevermind. I get it.

I don't think we can use strict subset on sets as an ordering for a
container. A strict subset relationship does not satisfy the minimum
ordering requirements of a strict weak ordering. See
http://www.sgi.com/Technology/STL/StrictWeakOrdering.html

For a strict weak ordering to hold, the following must be true:
!(x < y) && !(y < x) && !(y < z) && !(z < y) implies !(x < z) && !(z <
x))

Consider x = [ 'a' ], y = [ 'b' ], z = [ 'a' ].

Now consider a binary tree of the form:

          [ 'b' ]
          /     \
     [ 'c' ]   [ 'a' ]

If we do a search for [ 'c' ], how do we find it? Specifically, how do
we choose a direction when we compare to the root, [ 'b' ]?

Tyler


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com