From 4795053366876074070
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,e94695845965b249
X-Google-Attributes: gidf78e5,public
X-Google-ArrivalTime: 1992-12-16 07:43:15 PST
Newsgroups: comp.std.c++
Path: sparky!uunet!munnari.oz.au!metro!extro.ucc.su.OZ.AU!maxtal
From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Re: Zero-length structures and pointer comparisons
Message-ID: <1992Dec16.152718.8056@ucc.su.OZ.AU>
Sender: news@ucc.su.OZ.AU
Nntp-Posting-Host: extro.ucc.su.oz.au
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
References: <1992Dec11.212831.19493@bcrka451.bnr.ca> <5366@miramon.lulea.trab.se> <1992Dec14.230730.24452@microsoft.com>
Date: Wed, 16 Dec 1992 15:27:18 GMT
Lines: 71

In article <1992Dec14.230730.24452@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <5366@miramon.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>
>What if ptrcmp [addrcmp] were allowed to return 0 for those objects
>and/or systems that don't define an ordering for those objects?
>

	Given a set of pointers p1, p2, p3, and some function f,
we require that

	f(p1), f(p2), f(p3)

be a total order, and returning 0 always is clearly a trivial
total order *of f(p)* in that case.

	Dag wanted to have

	p1 == p2  <==> ptrcmp(p1,p2)==0    (DC)

and this imposes some constraint on 'f' which would certainly
mean that returning 0 always was not a total order.

Taking 'f' to be the underlying bits of a pointer makes 
ptrcmp fast and useful, but DC will not be satisfied on
the 8086.

The purpose of ptrcmp, surely, is to allow say sorting or btree
algorithms to be applied to pointers AT ALL. It really
doesnt matter what the order produced actually is.
What's important is that the damn algorithms 
work correctly, for example terminate in the case of a sort,
or retrieve the pointer from a btree.

A completely randomly chosen total order will work for
any algorithm not requiring equality tests.
Sorts not requiring uniqueness will work.

Btrees require uniqueness so wont. They need condition DC.
Otherwise they mnay fail to put some things into the tree
(thinking there is duplication) and put others in twice
(finding duplication where not intended).

So... how about TWO functions :-)

	anytorder(void*,void*); // might give 0 always
	obeysDC(void*,void*); // must obey DC above

Now it was ALSO suggested that if < implement a partial
order, the total order be compatible with it.
If I remember my maths, this can always be done
(assuming < is a partial order ... have to go back
to my maths books and 8086 manuals here :-)

Anyhow, can we list all the possible reasonable functions,
what properties they have, what the implications are, then
pick a standard set for inclusion in the library?

Furthermore, we can also have an optional set, the condition
is that they must have the listed properties IF they are
implemented, otherwise they must NOT be implemented.
(Or, they are all implemented, but might cause exceptions
if not defined .. if you know what I mean :-)

That ensures that correct code will either work or
fail gracefully, rather than yielding unexpected results.

-- 
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------