In article <1992Oct1.170427.8044@wam.umd.edu> krc@wam.umd.edu (Kevin R. Coombes) writes:
>In article <1992Sep29.160411.9737@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>>In article <1992Sep29.140750.29438@wam.umd.edu> krc@wam.umd.edu (Kevin R. Coombes) writes:
>>>[The]
>>> operator[](int index)
>>>should not be a member of a list class. Lists only provide sequential
>>>access; Arrays provide random access.
>>
>> I dont agree really. If you can get the first element,
>>and get the next element, then you can get the n'th element.
>>As far as I'm concerned, a list is an array with 'insert' and 'remove'
>                                 ^^^^
>>operations.
>
>Is that really an "IS-A"? Just like in public derivation of one class
>from another? Would  you write
>
>class List : public Array {
>  // ...
>};
>
>for example?

  Yes. Indeed:

 template<class T>
 struct array {
  virtual int operator+()const=0; // n elements
  virtual T& operator[](int)=0;
  virtual const T& operator[](int)const=0;
 };

 template<class T>
 struct list : public virtual array {
  virtual void insert(const T&,int);
  virtual void remove(int);
 };


>I'm just checking, because I don't want to read more into
>your statement than you may have intended. For me, an Array is primarily
>characterized by supplying constant-time random-access to any of its
>elements.

 So an array is a data structure. But my array is an abstraction.
No mention of contiguous storage. It is a map

 array: 0..n -> T,

in which n is constant, but the T elements are mutable.
A list is the same without the restriction on n.

I suppose I should have called it an extensible array, not a list.

>The two are equally primitive; one can be implemented
>in terms of the other; forcing a particular dependence or implementation
>seems to me to be to restrictive.
>

 I didnt even mention implementation. My 'array' and 'list'
are ADTs. It is mathematical nonsense to have a 'sequential
data structure'. If you can get the 'nth' element of a list,
then you can get the n'th element of the list.

 A genuine sequential access list would allow
only access to the top element, would have a destructive
next operator, and would not allow assignment or copying.

 If you can copy a list, you can get the n'th element.
If you can get the n'th element, why make it hard for the user?

 Anyhow, perhaps what I've done is used my own
private meanings for 'array' and 'list' as ADTs, certainly
the ability to insert and delete in the singly linked list
data structure influenced my decision to call an array
with insert and delete a list.

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