Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watdaisy.UUCP
Path: utzoo!watmath!watdaisy!gvcormack
From: gvcormack@watdaisy.UUCP (Gordon V. Cormack)
Newsgroups: net.lang,net.lang.pascal
Subject: Re: Why compare pointers in Pascal?
Message-ID: <6891@watdaisy.UUCP>
Date: Mon, 28-Jan-85 22:21:10 EST
Article-I.D.: watdaisy.6891
Posted: Mon Jan 28 22:21:10 1985
Date-Received: Tue, 29-Jan-85 06:06:40 EST
References: <3161@ucla-cs.ARPA> <335@snow.UUCP> <1920@wateng.UUCP>
Organization: U of Waterloo, Ontario
Lines: 13
Xref: watmath net.lang:1319 net.lang.pascal:211

> Say I had a set of records, which I represented as a vector of pointers.
> Suppose further that I wanted to test for set membership by comparing
> pointers. If I keep the vector sorted by increasing pointer value,
> I can do the test in O(lg(N)), using a binary search, but I need
> < and > on pointers. If all I have is == and !=, it takes O(N) time.
>    - peter bain

If one could get the representation of the pointer (say, as an integer)
one could test for membership in O(1) time using hashing.
-- 
 
Gordon V. Cormack      CS Department, University of Waterloo
   gvcormack@watdaisy.uucp     gvcormack%watdaisy@waterloo.csnet