Andrew received his M.S. degree in System Science from SUNY in Binghamton, N.Y. He has been programming for over 11 years and is interested in mathematical modeling, optimization, and computer simulations. He can be reached at 115 Filbert Road, Woodside, CA 94062, or at aed@netcom. UUCP.
A common problem in object-oriented design is creating and controlling collections, sets, or groups of objects. As object class designers, we'd ideally like to focus on the atomic aspects of the object abstraction, ignoring the secondary problem of maintaining and controlling collections of these objects. More importantly, we'd like to implement this control structure in a generic and reusable fashion.
This article presents a method for creating generic lists of objects in C++ with code developed on an Intel 80486, using GNU g++ 1.37 under SCO Unix System V, Release 3.2.
Generic Objects
Most algorithms described in books on data structures might be considered "generic" because they work for many types of data -- they're type-independent. Unfortunately, these books are more often than not written with procedural languages in mind, and we miss the generic (and code reusability) aspects of these algorithms. When we need one of these data structures, we usually have to reimplement the algorithm and data structure to fit our particular need.
To write a generic container class in any language, the language must provide some means of writing a general type-independent algorithm. One common complaint about C++ is that it does not support parameterized types, thereby making it difficult to create generic classes.
Parameterized types would allow you to easily write generic functions such as Max( ), which returns the greater of two values. Max( ) would contain the statement return( a > b ? a : b) and would work for any class or data type. (Future versions of C++ are supposed to support parameterized types.)
Currently, you can use overloading to create a Max( ) function for any class you may need, but that means rewriting the Max( ) function for each new class. The basic logic does not change, only the parameter list of the function. Using operator overloading in this example does not give us the code reusability or genericity we are after, but does make the code lexicographically simpler. Even if code reuse were not an issue, overloading still would not help as it works only for functions, not classes.
Inheriting the Problem
The $100 question, then, is how do we create a generic container class without parameterized types? In his book A C++ Toolkit, Jonathan S. Shapiro presents a design for a generic list based on inheritance. The only objection I have to this design is that it requires the class designer to decide what sort of containers the class will work with. Rather than place the burden of clairvoyance on the class designer, I would rather defer this decision to the user of the class. This frees the class designer to focus on the atomic aspects of object abstraction and ignore the secondary problem of how to maintain and control collections of these objects. It is very difficult to know how a class will be used in the future.
There is also another problem with creating container classes based on inheritance in C++. As a consequence of C++'s strong type checking, the container class will return a pointer or reference to a container, instead of to the object the container class is supposed to control. To get around this problem, you can cast the returned pointer to the class of the object, but you should not have to do this.
Stephen Dewhurst and Kathy Stark (Programming in C++) also present an almost fully generic design for linked lists using typedefs to support various data types. The problem with this approach is that their generic list will support only one type of class in any given program. For example, assume we have two classes -- one representing coins, and the other representing colors. It should be possible to have a list of coins and a separate list of colors in the same file scope, without the coin class and the color class having to share a common base class.
Solving the Generic Problem
The design I present here is a more generic version of Dewhurst and Stark's generic list and gets around the problem of maintaining a separate list within the same file scope. Dewhurst and Stark implement the linked list using item, list, and iter classes. The item class contains a pointer to the next item and a reference to the object to be controlled using the list. The list class contains a pointer to the head of the list and member functions for clearing, appending, and inserting objects into the list. The iter class is used to provide a control abstraction, which retains the state of the iteration from invocation to invocation. The test programs described later illustrate how to use these three classes.
Generic.h, which is included in C++ 2.0, contains a set of macro functions that can be expanded to create a unique set of container class definitions for each class to be controlled. The macro functions will entirely encapsulate and hide the implementation of the container class. Specifically, Generic.h contains a name2() macro function that takes two arguments and concatenates them. For example, name2(foo, blort) expands to be fooblort. name2() is used to create a unique name for each type of list required. For each generic class needed, define a macro function that will take one argument representing the class to be controlled. Listing One (page 124) #defines the GenList class. Once defined, the GenList macro can create a generic list of coins using GenList(coin) ListOfCoins;. The C Preprocessor (CPP) will convert this to coinGenList listOfCoins;.
With the name part of the problem solved, all that's left is defining the data members and member function for the GenList(CLASS_TAG). Generic.h provides another macro function, declare( ), to help with this problem. To declare the class definition for the generic list-class of coins, use declare(GenList,coin);. CPP will expand this into GenList-declare(coin);, a programmer-defined macro function. In fact, this is where you'll write all generic algorithms pertaining to the list class. GenListdeclare( ) is typical of the macro function names generated by declare( ); its form is shown in Figure 1. In examining Figure 1, recall that the backslash character (\) is used to continue the macro on the next line. Anytime I need the name of the generic class, I use the corresponding name macro function.
Figure 1: The GenListdeclare macro function
#define GenListdeclare (CLASS_TAG \
class GenList (CLASS_TAG) \
{ \
private: \
public: \
/* the default constructor */ \
GenList (CLASS_TAG)() \
{ \
... \
} \
}
At this point, you should have enough background to browse Listing One. I have also provided test1.cc (see Listing Two, page 124), coin.hh (Listing Three, page 124), and coin.cc ( Listing Four, page 125) to provide an example of actual use. Also provided is preproc.cc (Listing Five, page 125), which shows how the actual macro function is expanded for the coin class.
Improvements
I implemented the generic list using references. You may choose to keep a copy of the object in your version of the item class. I decided to use references because my application controls static objects. By using references, I save memory. (I have only one copy of the object instead of possibly two.) The code should also run faster because there will be fewer calls to the object's constructors and destructors. Keep in mind that every time you put an object on the stack, the compiler automatically makes a call to the object's copy constructor. If the object is derived, this can add significantly to the number of function calls made.
A disadvantage of using references instead of maintaining a copy is that it's possible to have dangling references. Before an object in the list is destroyed, it must be removed from the list. Failure to do so will render the list useless. The test program gives an example of this. This can easily occur if, for example, two lists are set equal to one another and then passed to different sub-systems.
Users of the generic list may choose to split the declare macro into two. One macro would define the generic class data members and member functions. The other macro function would implement the actual member functions. There are two advantages to this approach. The first advantage is that this version will work with C++ compilers that are based on cfront. The second advantage is that you will eliminate link errors that occur when two modules try to use generic lists on the same class of objects.
There are several member functions that you could add to the generic list family of classes. Dewhurst and Stark mention the possible addition of an apply function in which there is a member or friend function that you wish to "apply" to all of the objects in the list. The user of the list can easily implement this in a few lines of code using the iter class.
I found that adding the apply function to the list class can become unruly. For example, I had to overload the apply function to handle member and friend functions that take a variable number of arguments. If you plan to implement this feature, declare the pointers to the functions as taking a variable number of arguments and provide two versions of the apply function: one for the member functions, the other for the friend functions.
Of course, there's always a flip side to the coin, and in this case the disadvantage is that you lose the benefits of type checking. Nevertheless, the generic list container class presented in this article should provide a good starting point -- and may this wheel never be invented again.
Endnotes
Jonathan S. Shapiro, A C++ Toolkit. Englewood Cliffs, N.J.: Prentice-Hall, 1991.
Stephen C. Dewhurst and Kathy T. Stark, Programming in C++. Englewood Cliffs, N.J.: Prentice Hall, 1989.
References
Lippman, Stanley B. C++ Primer. Reading, Mass.: Addison-Wesley, 1989.
Stubbs, Daniel F. and Webre, Neil W. Data Structures with Abstract Data Types and Pascal. Monterey, Calif.: Brooks/ Cole Publishing Company, 1985.
_GENERIC CONTAINERS IN C++_ by Andrew Davidson[LISTING ONE]
<a name="01c6_000c">
/*
* Generic list
*
* by A. E. Davidson 12/90
*
* Overview
*
* USES
* to declare a generic list of class
* foo items and a generic list of class
* bar items
*
* #include "genriclt.hh"
* DeclareList(Foo);
* DeclareList(Bar);
*
* main()
* {
* class foo;
* class bar;
* GenList(foo) genListOfFoo;
* GenList(bar) genListOfBar;
* GenIter
*
* REQUIREMENTS / ASSUMPTIONS
* The generic list does not manage
* the items memory. It is up to the
* user to free them
*
* the function GenList::RemoveItem()
* takes a pointer to a member function.
* this funciton should return true is found
* else false. GenList::RemoveItem will not
* compile on my machine if the member
* fuction is inlined. it gives a signal 6 error message
*
* NOTES
* never use new to create a list or an iter!
*
*
*/
#include <generic.h>
#ifndef GENERIC_LIST_HH
#define GENERIC_LIST_HH
/*
* these macro's should be used
* any where you need to reffer to
* the generic list, item, or iter classes
*
* PTAMF: Pointer to a Member Function
*/
#define PTAMF(CLASS_TAG) name2(CLASS_TAG,PTAMF)
#define GenItem(CLASS_TAG) name2(CLASS_TAG,GenItem)
#define GenList(CLASS_TAG) name2(CLASS_TAG,GenList)
#define GenIter(CLASS_TAG) name2(CLASS_TAG,GenIter)
/*----------------------------- class Item ---------------------------*/
/*
* GenItem(CLASS_TAG) is a private
* class. It can only be created by
* be the member functions of GenList(CLASS_TAG)
* and GenIter(CLASS_TAG)
*/
#define GenItemdeclare(CLASS_TAG) \
class GenItem(CLASS_TAG) \
{ \
GenItem(CLASS_TAG) *next; \
CLASS_TAG &item; \
GenItem(CLASS_TAG)(CLASS_TAG &i) : item(i) \
{next = NULL;} \
GenItem(CLASS_TAG)(CLASS_TAG &i, GenItem(CLASS_TAG) *n) : item(i) \
{next = n; } \
~GenItem(CLASS_TAG)() \
{;} \
friend GenList(CLASS_TAG); \
friend GenIter(CLASS_TAG); \
}
/*---------------------------- class List ---------------------------*/
#define GenListdeclare(CLASS_TAG) \
class GenList(CLASS_TAG) \
{ \
GenItem(CLASS_TAG) *hd; \
public: \
GenList(CLASS_TAG)(GenItem(CLASS_TAG) *n = NULL) \
{ hd = n;} \
GenList(CLASS_TAG)(const CLASS_TAG &i) \
{hd = NULL; insert(i);} \
~GenList(CLASS_TAG)() \
{Clear();} \
void Clear(void) \
{ \
GenItem(CLASS_TAG) *pt; \
while (hd) \
{ \
pt = hd; \
hd = hd->next; \
delete pt; \
} \
} \
GenList(CLASS_TAG)(const GenList(CLASS_TAG) &seq) {hd = seq.hd;} \
GenList(CLASS_TAG) operator = (const GenList(CLASS_TAG) &other) \
{ \
hd = other.hd; \
return *this; \
} \
void insert(CLASS_TAG &i){ hd = new GenItem(CLASS_TAG)(i, hd); } \
void append(CLASS_TAG &i) \
{ \
for (GenItem(CLASS_TAG) *pt = hd; pt && pt ->next; pt = pt->next) \
; \
if (pt) \
{ \
GenItem(CLASS_TAG) *tmp = new GenItem(CLASS_TAG)(i); \
pt->next = tmp; \
} \
else insert(i); \
} \
\
void removeItem(PTAMF(CLASS_TAG) found, CLASS_TAG &obj) \
{ \
GenItem(CLASS_TAG) *prev, *rem; \
\
prev = NULL; \
rem = hd; \
while( rem && !(obj.*found)(rem->item) ) \
{ \
prev = rem; \
rem = rem->next; \
} \
if (rem) \
{ \
if (prev) \
prev->next = rem->next; \
else \
hd = rem->next; \
delete rem; \
} \
} \
friend GenIter(CLASS_TAG); \
}
/*------------------------------- class Iter ---------------------------*/
/*
* interate over entire list
* CLASS_TAG *operator()()
*/
#define GenIterdeclare(CLASS_TAG) \
class GenIter(CLASS_TAG) \
{ \
GenItem(CLASS_TAG) *current; \
public: \
GenIter(CLASS_TAG)(GenList(CLASS_TAG) &ilist) \
{ current = ilist.hd; } \
GenIter(CLASS_TAG)(GenIter(CLASS_TAG) &other) \
{ current = other.current; } \
~GenIter(CLASS_TAG)() \
{;} \
GenIter(CLASS_TAG) operator = (GenList(CLASS_TAG) &ilist) \
{ current = ilist.hd; return *this; } \
CLASS_TAG *operator()() \
{ \
if (current) \
{ \
GenItem(CLASS_TAG) *tmp = current; \
current = current->next; \
return &tmp->item; \
} \
return NULL; \
} \
}
/*
* macro that create all the generic types
* provided for ease of uses
*
* for some unknown reason my compiler can't handle a
* function prameter that is a pointer to a member function
* It can deal with it if the pointer is declared using
* a typedef
*/
#define DeclareList(CLASS_TAG) \
typedef int (CLASS_TAG::*PTAMF(CLASS_TAG))(CLASS_TAG &); \
class GenList(CLASS_TAG); \
class GenIter(CLASS_TAG); \
declare(GenItem,CLASS_TAG); \
declare(GenList,CLASS_TAG); \
declare(GenIter,CLASS_TAG)
#endif
<a name="01c6_000d">
<a name="01c6_000e">[LISTING TWO]<a name="01c6_000e">
/*
* test1.cc
*
* by A. E. Davidson
*
* Provides a driver to test the generic list
*/
#include <stream.h>
#include "coin.hh"
#include "genericl.hh"
/*
* use the declare macros to
* allow creation of list of desired types
*/
DeclareList(coin);
/*
* proto typing function using the generic list
* stuff must be done after DeclareList()
*/
void displayAndTotal(GenIter(coin) next_coin);
main()
{
/*--- create some coins -------*/
coin c1 = penny;
coin c2 = nickel;
coin c3 = dime;
coin c4 = quarter;
/*------ create a list of coins -----*/
GenList(coin) list_of_coins;
list_of_coins.append(c1);
list_of_coins.append(c2);
list_of_coins.append(c3);
list_of_coins.append(c4);
/*------- display the list of coins and there total ------*/
displayAndTotal(list_of_coins);
/*-------------- remove one of the coins --------------*/
cout << "\n\n list after removing coin c2 \n";
list_of_coins.removeItem(&coin::found, c2);
displayAndTotal(list_of_coins);
/*
* rember: c2 has been removed from the list but it still exists
*/
cout << "\n\n coin c2 still exists, it was only removed from the list \n";
cout << "coin: " << c2;
#ifdef NEVER
/*
* this is example shows a design flaw
* with the generic list assignment operator
*
* if you delete an object but do not remove it
* from the list first you will get a core dump.
* The list will contain a dangling reference
*
* this is becuase I chose to implement the
* the list using references instead of copying
* the objects. See the discusion at the end of the
* article
*/
coin *c5 = new coin(quarter);
list_of_coins.append(*c5);
delete c5;
displayAndTotal(list_of_coins);
#endif
}
/*
* this function illustrates
* how to use the GenIter class
*
* notice that the parmeter list expect
* an inter object, but I always pass a list
* object
*/
void displayAndTotal(GenIter(coin) next_coin)
{
double total = 0.0;
coin *tmp;
while ((tmp = next_coin()))
{
/*
* coins know how to convert themselves to doubles
*/
total += *tmp;
/*
* coins also know how to display themselves
*/
cout << "coin: " << *tmp << "\ttotal: " << total <<"\n";
}
}
<a name="01c6_000f">
<a name="01c6_0010">[LISTING THREE]<a name="01c6_0010">
/*
* coin class
*
* by A. E. Davidson
*
* USES
* provides a simple class that can be
* used to illistrate the operation of
* the generic list
*
* a coin may be a penny, nickel, dime, or quarter
*/
#ifndef COIN_HH
#define COIN_HH
enum coin_type {penny, nickel, dime, quarter};
class coin
{
coin_type unit;
double amount;
public:
coin()
{unit = penny; amount = 0.01;}
coin( coin_type type);
coin(const coin &other)
{unit = other.unit; amount = other.amount;}
~coin(){;}
coin& operator = (const coin &other)
{ unit = other.unit; amount = other.amount;}
friend ostream& operator << (ostream &os, coin &c);
operator double ()
{return amount;}
/*
* this function is intended to be
* used with GenList(CLASS_TAG)::removeItem()
* I get a compile error if I try to inline this
* function
*/
int found(const coin &other);
};
#endif
<a name="01c6_0011">
<a name="01c6_0012">[LISTING FOUR]<a name="01c6_0012">
#include "stream.h"
#include "coin.hh"
char *coin_name[] = {"penny", "nickel", "dime", "quarter"} ;
/*
* convenient look up table
* keeps from having to duplicate case statements any
* time you need to work with unit data member
*/
static struct
{
coin_type kind;
double amount;
} table [] =
{
{penny, 0.01},
{nickel, 0.05},
{dime, 0.10},
{quarter, 0.25},
{quarter, 0.0}, /* end of the table */
};
coin::coin(coin_type type)
{
unit = type;
for (int i = 0; table[i].amount != 0.0 && unit != table[i].kind; i++)
;
amount = table[i].amount;
}
ostream& operator << (ostream &os, coin &c)
{
os << coin_name[c.unit];
return os;
}
int coin::found(const coin &other)
{
return (unit == other.unit);
}
<a name="01c6_0013">
<a name="01c6_0014">[LISTING FIVE]<a name="01c6_0014">
/*
* this is the output from CPP
* g++ -E test1.cc
*
* I reformated the output to make it
* easier to read
*/
typedef int (coin::* coinPTAMF )(coin &);
class coinGenList ;
class coinGenIter ;
class coinGenItem
{
coinGenItem *next;
coin &item;
coinGenItem (coin &i) : item(i)
{next = 0 ;}
coinGenItem (coin &i, coinGenItem *n) : item(i)
{next = n; } ~coinGenItem ()
{;}
friend coinGenList ;
friend coinGenIter ;
} ;
class coinGenList
{
coinGenItem *hd;
public:
coinGenList (coinGenItem *n = 0 )
{ hd = n;}
coinGenList (const coin &i)
{hd = 0 ; insert(i);}
~coinGenList ()
{Clear();}
void Clear(void)
{
coinGenItem *pt;
while (hd)
{
pt = hd;
hd = hd->next;
delete pt;
}
}
coinGenList (const coinGenList &seq)
{hd = seq.hd;}
coinGenList operator = (const coinGenList &other)
{ hd = other.hd; return *this; }
void insert(coin &i)
{ hd = new coinGenItem (i, hd); }
void append(coin &i)
{
for (coinGenItem *pt = hd; pt && pt ->next; pt = pt->next)
;
if (pt)
{
coinGenItem *tmp = new coinGenItem (i);
pt->next = tmp;
}
else
insert(i);
}
void removeItem( coinPTAMF found, coin &obj)
{
coinGenItem *prev, *rem;
prev = 0 ;
rem = hd;
while( rem && !(obj.*found)(rem->item) )
{
prev = rem;
rem = rem->next;
}
if (rem)
{
if (prev)
prev->next = rem->next;
else
hd = rem->next;
delete rem;
}
}
friend coinGenIter ;
} ;
class coinGenIter
{
coinGenItem *current;
public:
coinGenIter (coinGenList &ilist)
{ current = ilist.hd; }
coinGenIter (coinGenIter &other)
{ current = other.current; }
~coinGenIter () {;}
coinGenIter operator = (coinGenList &ilist)
{ current = ilist.hd; return *this; }
coin *operator()()
{
if (current)
{
coinGenItem *tmp = current;
current = current->next;
return &tmp->item;
} return 0 ;
}
} ;
void displayAndTotal(coinGenIter next_coin);
main()
{
coin c1 = penny;
coin c2 = nickel;
coin c3 = dime;
coin c4 = quarter;
coinGenList list_of_coins;
list_of_coins.append(c1);
list_of_coins.append(c2);
list_of_coins.append(c3);
list_of_coins.append(c4);
displayAndTotal(list_of_coins);
cout << "\n\n list after removing coin c2 \n";
list_of_coins.removeItem(&coin::found, c2);
displayAndTotal(list_of_coins);
cout << "\n\n coin c2 still exists, it was only removed from the list \n";
cout << "coin: " << c2;
# 78 "test1.cc"
}
void displayAndTotal(coinGenIter next_coin)
{
double total = 0.0;
coin *tmp;
while ((tmp = next_coin()))
{
total += *tmp;
cout << "coin: " << *tmp << "\ttotal: " << total <<"\n";
}
}
[MAKEFILE]
CC= g++
OBJS= coin.o test1.o
SRCS = coin.cc test1.cc
LIBS= -lg++ -lm
INCLUDE= -I/n/catserv/usr1/tools/sun4/usr/local/lib/g++-include
.SUFFIXES: .cc
.cc.o:
$(CC) -c -g $<
coinTest : $(OBJS) coin.hh genericlt.hh
$(CC) -o $@ -g $(OBJS) $(LIBS)
clean :
rm -f coinTest *.o
#
# notes
#
#
# $@ the name of the current target
#
#
# $< the name of a dependency file, derived as if selected
# for use with an implicit rule
#
depend :
makedepend -- $(CFLAGS) -- $(INCLUDE) -- $(SRCS)
# DO NOT DELETE THIS LINE -- make depend depends on it.
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stream.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/ostream.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/File.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/builtin.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stddef.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/std.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stdio.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/math.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/values.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/streambuf.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/istream.h
coin.o: coin.hh
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stream.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/ostream.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/File.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/builtin.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stddef.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/std.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stdio.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/math.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/values.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/streambuf.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/istream.h
test1.o: coin.hh genericlt.hh
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/generic.h
Copyright © 1991, Dr. Dobb's Journal
