Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!caen!uwm.edu!ogicse!orstcs!fog.CS.ORST.EDU!budd
From: budd@fog.cs.orst.edu (Tim Budd)
Newsgroups: comp.lang.c++
Subject: Common data structures
Keywords: list, data structures, c++
Message-ID: <1991Jun10.200429.26713@lynx.CS.ORST.EDU>
Date: 10 Jun 91 20:04:29 GMT
Sender: @lynx.CS.ORST.EDU
Organization: Computer Science Department, Oregon State Univ.
Lines: 44
Originator: budd@fog.CS.ORST.EDU
Nntp-Posting-Host: fog.cs.orst.edu

I was surprized that Jean-Ren Bouvier's request for a simple ``List'' data
structure generated so little discussion.   Surely this must be one of the
most common programs written in C++.  But that is not to say it is easy to
do.  In my book ``An Introduction to Object-Oriented Programming'' I tried
to create just such classes (Chapter 17).  I was somewhat dissatisfied with
the result, and seemingly a few readers were as well.  So recently I
returned to the problem.

My objectives were as follows:

1) The data structures created should be small and easy to understand.

2) Use of the data structure classes should not imply nor prohibit use of 
any other classes.  That is, using the data structure classes should not
force you into using a particular memory management package, or whatever.

3) They should not make any restriction on the type of values they contain.
For example they should not require that all values held in the data
structures be subclasses of a specific class.  [ This was the constraint I
voilated in my original Chapter 17, and one violated in many other examples
I have seen].

4) The solution should *not* use templates, but should be *guaranteed*
type-safe.  That is, it should be possible to guarantee that any casts used
(and clearly some casts will be necessary) are type-safe.
[ Avoiding templates was not a philosophical decision - I merely wanted to
show it could be done, and easily done at that].

5) It should be possible to manipulate the data structures, for example 
iterating over the elements of a list, without any knowledge of the
internal structure of the data structure.

Anyway.  To make a long story short, you can obtain the fruits of my labors
via an automatic mail server.  I've written classes for lists (ordered and
unordered), sets, stacks, queues, trees and tables.  I will probably be
adding to this as times goes on.
Send a note to ``oopintro@cs.orst.edu'' with
subject line ``Generic'' to obtain the code and a latex description.
I would be interested in feedback on either code or document.
Note that mail to ``oopintro'' is not read by human beings, if you want to
reach me personally my address is below.

--tim budd
budd@cs.orst.edu