From: kanze@us-es.sel.de (James Kanze)
Subject: Re: Sigh. So, what is a proper class definition ?
Organization: SEL
	<KANZE.92Sep29202632@slsvcgt.us-es.sel.de>
	<1992Oct1.153940.17328@ucc.su.OZ.AU>
Date: 7 Oct 92 18:58:18

In article <1992Oct1.153940.17328@ucc.su.OZ.AU>
maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

> In article <KANZE.92Sep29202632@slsvcgt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
> >In article <1992Sep23.162216.21027@ucc.su.OZ.AU>
> >maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
> >
> >> 	A list is an array with insert and remove operators.
> >> Arrays have [] access and a length operator. I dont bother
> >> with iterators for lists---integers do just fine. This
> >> approach is inefficient, but a cache can improve that.
> >> (If I really want ultra fast access I can use 'first' and 'next',
> >> but I hardly ever bother)
> >
> >And what happens if efficiency later becomes important.

> 	I thought I said: attach a cache to the list. Or reimplement
> the list as doublely linked.

> 	What do YOU do if you want to read the list backwards?
> Woops, you have to write some special code, every time.
> I just read it backwards. I dont make any assumptions about
> the physical list organisation. I treat the list as an
> Abstract Data Type.

But a list is a list, a specific type of abstract data type.  As such,
it is designed for sequential access, not random.

I do understand the idea of treating a list as an array, and there are
no doubt cases where such handling is justified, but if you want to
access the ith member, I doubt that a list is the correct data
structure.

> 	Besides, I *also* supply 'first' and 'next' which
> return pointers, and they're even faster than an iterator.

And of course, if you wrote the code using "int" as an iterator, you
have to modify it to get the speed advantage.  Whereas if the "int"
had been encapsulated in an iterator class, you modify the iterator
class to use the pointers, and user code never sees a thing.

> >I almost never use int (for anything).  It's almost always better to
> >whip up a small class.  How much work would it be to encapsulate your
> >int in an iterator class?  And if efficiency does become important,
> >re-implement the iterator class in a more efficient manner.  Without
> >breaking any code that uses it.
> >
> >Once you've used int as the iterator, you're stuck.  Any improvements
> >break user code.

> 	On the contrary, once you use a sequential iterator you're
> stuck. Then you can ONLY read the list in sequence. But that is
> absurd because mathematically that IMPLIES random access.
> So the sequential nature of a list is usually an artefact
> of the most efficient access method, which is not a very
> good criterion for abstract class design.

Again, a list is basically a *sequential* data structure.  If you
design a class with random access, please don't call it a list.
(Array or vector would be good names.)  Note that in an array (or
vector), speaking of the nth entry has an absolute mathematical sense.
In a list (mathematically, a sequence), the nth member is only defined
as the member that follows the n-1th.

The sequential nature of a list is inherent in its definition.  We
then choose an implementation that favorizes this type of access.  You
should not design the other way around.

> 	A second advantage of integers for iterators is that
> they can be used to iterate lists in parallel. A third advantage
> is that insertions and deletions into the list are safe at
> all times (provided the integer index is compared with the length
> of the list before each access) although the effect may not
> be what is desired!

As you say, insertions and deletions may not have the effect desired
when iterating with an int.  Again, this is an advantage of
encapsulating the int in an iterator object.  If it later becomes
necessary to support such operations correctly, then you modify the
iterator to support them.  Code already using the iterator does not
require modification to adapt to a new philosophy of iteration.

> 	But the principal advantage is simplicity: as a list
> is just like an array, it is accessed accordingly. Any routine
> coded for an array will work on a list. (BTW, I mean by
> array something accessed by a[i], and which has a determinable
> length).

> 	I can write: (+a is the no of elts in a)

> 	for(int i=0; i<+a; ++i) { ... a[i]; ... }

> 	and it always terminates, and every access to a is in bounds.
> (provided a[i] and all elts to the end are not deleted prior to another
> access to a[i])

> >BTW, I'm not saying that the lack of efficiency is bad.  Just
> >encapsulate it so you can change later, without too much effort.

> 	I agree. Its just that I've encapsulated something different
> to an iterator or single linked list with sequential access.
> I've encapsulated the idea of an array with insert and delete
> operations.

Yes, but if this type of access is really important (and the type is
not really physically an array), then maybe you should encapsulate the
notion of an array index.

If the "int" index is only used as an iterator, create an iterator
class to encapsulate it.

If the "int" actually comes from somewhere else, then of course, you
have to think about how it is mapped into the class.  If the nature of
the problem requires accessing with a random integer index, then
implement it, by all means.  (However, if this is so, I wonder if a
list is really the correct fundamental type for the application.)

> 	As an abstraction this is a great base for 'stack',
> 'queue', etc. And for subsequent addition of iterators.
> Perhaps I should have called it something other than 'list'.

This may be part of the problem.  On my current projects, there are a
great number of sets implemented by single linked lists.  This works
out OK, as they rarely contain more than two or three elements.
Regretfully, they use an int as iterator.  (They were designed before
I arrived on the project:-).)  If any one of these sets is ever
required to contain a really large number of objects, a lot of code
will have to be rewritten.  And of course, it is impossible to
iterate and remove any elements meeting a certain criteria.
--
James Kanze                     GABI Software, Sarl.
email: kanze@us-es.sel.de       8 rue du Faisan
                                67000 Strasbourg
                                France
Newsgroups: comp.lang.c++