But strong typing makes development of reusable collection
(or container) classes difficult
Conventional Solution
Conventional containers closely tie the container and the element type
type
Link =
Record
value : integer;
nextELement : ^ Link;
end;
Containers in Dynamic Languages
Common Base Link Type
The Generic List Class
class List {
public:
// constructor
List() : firstElement(0)
{ }
// operations
void Add(Link
* n)
{ n->next = firstElement; firstElement = n; }
int isEmpty()
{ return firstElement == 0; }
Link * First();
{ return firstElement; }
void
RemoveFirst();
{ Link * p = firstElement;
firstElement = firstElement-> next;
delete p; }
int Includes(Link
* n)
{ for (Link * p = firstElement; p; p = p->next)
if (*p == *n) return 1;
return 0; }
private:
// data field
Link * firstElement;
};
class
Link {
public:
// constructors
Link () :
next(0) { }
Link (Link
* n) : next(n) { }
// operations
virtual int
operator == (Link *) = 0;
// data field
Link * next;
};
A Link for Double Precision Numbers
class DoubleLink : public Link {
public:
// data area
double theValue;
// constructor
DoubleLink
(double v) : theValue(v) {}
// operations
int operator
== (Link * d)
{ return thisValue == ((DoubleLink *) d)->theValue; }
};
Using the List Class
Using the list class involves explicitly creating links.
List aList;
aList.Add(new DoubleLink(2.71828));
aList.Add(new DoubleLink(1.61803));
aList.Add(new DoubleLink(3.14159));
DoubleLink * pi;
pi = (DoubleLink *) aList.First();
aList.RemoveFirst();
Hiding the Links
Can avoid explicit manipulation of links by subclassing
the List class as well.
class DoubleList : public List {
public:
void Add(double
v)
{ List::add(new DoubleLink(v)); }
double First()
{ return firstElement->value; }
int Includes(double
v)
{ DoubleLink v1(v);
return List::includes(v1); }
};
Containers that Hold Only Pointers
class List {
public:
... // same
as before
void Add(void
* v)
{ firstElement = new Link(v, firstElement); }
void * First()
{ return firstElement->value; }
... // same
as before
};
class Link {
// constructors
Link (void
* v) : next(0), value(v) {}
Link (void
* v, Link * n) : next(n), value(v) {}
// data areas
Link * next;
void * value;
};
Example: list of Windows
class WindowList : public List {
public:
void Add(Window
* w)
{ List::add(w); }
Window * First()
{ return (Window *) List::first(); }
};
A Template List Class
template <class T>
class List {
// constructors
List();
// operations
void Add(T
v)
{ firstElement = new Link<T>(v, firstElement); }
int isEmpty()
{ return firstElement == 0; }
T First()
{ return firstElement->value; }
void RemoveFirst()
{ Link<T> * p = firstElement;
firstElement = p->next;
delete p; }
int Includes(T
v)
{ for (Link<T> * p = firstElement; p; p = p->next)
if (v == p->value)
return 1;
return 0; }
};
template <class T>
class Link {
// constructor
Link (T v,
Link * n) : value(v), next(n) { }
// data fields
Link * next;
T value;
};
Using Template Classes
List<double> aList;
aList.Add(2.71828);
aList.Add(1.61803);
aList.Add(3.14159);
double pi;
pi = aList.First();
aList.removeFirst();
Iteration and Iterators
Want mechanism for iteration over containers of values without exposing implementation
Can be performed using an iterator
In C++ can be made to look like a pointer
list<int>::iterator start = aList.begin();
list<int>::iterator end = aList.end();
for ( ; start != end; ++start)
cout <<
(*start) << endl;
Iterator Class
template <class T> class listIterator {
ListIterator (Link<T> & sl)
: currentLink(sl) { }
void operator ++ () { currentLink = currentLink->nextLink; }
T operator * () { return currentLink->value; }
bool operator == (ListIterator<T>
& right)
{ return currentLink ==
right.currentLink; }
private:
Link<T>
* currentLink;
};
Containers in Java