Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!amdahl!pyramid!leadsv!esl!dml
From: dml@esl.UUCP (Denis Lynch)
Newsgroups: comp.lang.c++
Subject: Re: Friend specifier considered harmful
Message-ID: <763@esl.UUCP>
Date: 17 Sep 88 04:56:24 GMT
References: <61@cybaswan.UUCP> <1988Sep2.174327.6439@ateng.uucp> <78@cybaswan.UUCP> <1988Sep15.151514.20657@ateng.uucp>
Reply-To: dml@esl.UUCP (Denis Lynch)
Organization: ESL, Inc., Sunnyvale, CA.
Lines: 39

In article <1988Sep15.151514.20657@ateng.uucp> chip@ateng.UUCP (Chip Salzenberg) writes:
>>Why this structure anyway?  --- it's the C approach, not C++!  You ought to
>>have an array of lists in HashTable, with the lists carrying HashNode objects
>>without a next field.
>
>But you're wrong!  Linked lists are a useful data structure no matter what
>the language.

But you missed the point. Of course linked lists are useful. They are
a separate concept of their own, and shouldn't be imbedded in you hash
table constructs. You want a hash table to be a sequence (list, array,
file, shouldn't matter to even the top level of HashTable), where each
element in the sequence can in turn be a set or sequence (I don't know
which, maybe order matters to you.) The HashNode isn't the thing that
really has the "next" property, that is the responsibility of the set
or sequence.

The big difference here is what happens when you try to use your hash
node: suppose for some reason I need to keep a list of the most
recently used hash nodes. Sounds like I want to use the next field,
right? If it is designed as suggested above, you can see that a
HashNode can appear on multiple lists without getting confused.

In short, look at something like OOPS. Use a set of basic "computer
science" classes to handle lists, arrays, sets, etc., independent of
the *contents* of the collections.

>...Although I find it interesting that the interface I used would permit
>changing to arrays instead of linked lists without modifying the HashTable
>interface at all.  This is a good sign.

And if you follow these recommendations, the only thing you would need
to change is the initialization method, since the insertion/access
methods would be the same for arrays, lists, and other things.

-- 
Denis Lynch                          
ESL Incorporated                         decwrl!borealis!\
ARPA: dml%esl.ESL.COM@ames.arc.nasa.gov    ucbcad!ucbvax!- ames!- esl!dml
SMAIL: dml@esl.ESL.COM                                  lll-lcc!/