Inapoi
Inainte
Cuprins
Stack and Stash
as
templates
The recurring
“ownership” problems with the Stash and Stack
container classes that have been revisited throughout this book come from the
fact that these containers haven’t been able to know exactly what types
they hold. The nearest they’ve come is the Stack “container
of Object” that was seen at the end of Chapter 15 in
OStackTest.cpp.
If the client programmer doesn’t
explicitly remove all the pointers to objects that are held in the container,
then the container should be able to correctly delete those pointers. That is to
say, the container “owns” any objects that haven’t been
removed, and is thus responsible for cleaning them up. The snag has been that
cleanup requires knowing the type of the object, and creating a generic
container class requires not knowing the type of the object. With
templates, however, we can write code that doesn’t know the type of the
object, and easily instantiate a new version of that container for every type
that we want to contain. The individual instantiated containers do know
the type of objects they hold and can thus call the correct destructor
(assuming, in the typical case where polymorphism is involved, that a virtual
destructor has been provided).
For the Stack this turns out to be
quite simple since all of the member functions can be reasonably
inlined:
//: C16:TStack.h
// The Stack as a template
#ifndef TSTACK_H
#define TSTACK_H
template<class T>
class Stack {
struct Link {
T* data;
Link* next;
Link(T* dat, Link* nxt):
data(dat), next(nxt) {}
}* head;
public:
Stack() : head(0) {}
~Stack(){
while(head)
delete pop();
}
void push(T* dat) {
head = new Link(dat, head);
}
T* peek() const {
return head ? head->data : 0;
}
T* pop(){
if(head == 0) return 0;
T* result = head->data;
Link* oldHead = head;
head = head->next;
delete oldHead;
return result;
}
};
#endif // TSTACK_H ///:~
If you compare this to the
OStack.h example at the end of Chapter 15, you will see that Stack
is virtually identical, except that Object has been replaced with
T. The test program is also nearly identical, except that the necessity
for multiply-inheriting from string and Object (and even the need
for Object itself) has been eliminated. Now there is no MyString
class to announce its destruction, so a small new class is added to show a
Stack container cleaning up its objects:
//: C16:TStackTest.cpp
//{T} TStackTest.cpp
#include "TStack.h"
#include "../require.h"
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
class X {
public:
virtual ~X() { cout << "~X " << endl; }
};
int main(int argc, char* argv[]) {
requireArgs(argc, 1); // File name is argument
ifstream in(argv[1]);
assure(in, argv[1]);
Stack<string> textlines;
string line;
// Read file and store lines in the Stack:
while(getline(in, line))
textlines.push(new string(line));
// Pop some lines from the stack:
string* s;
for(int i = 0; i < 10; i++) {
if((s = (string*)textlines.pop())==0) break;
cout << *s << endl;
delete s;
} // The destructor deletes the other strings.
// Show that correct destruction happens:
Stack<X> xx;
for(int j = 0; j < 10; j++)
xx.push(new X);
} ///:~
The
destructor for X is
virtual, not because it’s necessary here, but because xx could
later be used to hold objects derived from X.
Notice how easy it is to create different
kinds of Stacks for string and for X. Because of the
template, you get the best of both worlds: the ease of use of the Stack
class along with proper cleanup.
Templatized pointer Stash
Reorganizing the PStash code into
a template isn’t quite so simple because there are a number of member
functions that should not be
inlined. However, as a template
those function definitions still belong in the
header file (the compiler and
linker take care of any multiple definition problems). The code looks quite
similar to the ordinary PStash except that you’ll notice the size
of the increment (used by inflate( )) has been templatized as a
non-class parameter with a default value, so that the increment size can be
modified at the point of instantiation (notice that this means that the
increment size is fixed; you may also argue that the increment size should be
changeable throughout the lifetime of the object):
//: C16:TPStash.h
#ifndef TPSTASH_H
#define TPSTASH_H
template<class T, int incr = 10>
class PStash {
int quantity; // Number of storage spaces
int next; // Next empty space
T** storage;
void inflate(int increase = incr);
public:
PStash() : quantity(0), next(0), storage(0) {}
~PStash();
int add(T* element);
T* operator[](int index) const; // Fetch
// Remove the reference from this PStash:
T* remove(int index);
// Number of elements in Stash:
int count() const { return next; }
};
template<class T, int incr>
int PStash<T, incr>::add(T* element) {
if(next >= quantity)
inflate(incr);
storage[next++] = element;
return(next - 1); // Index number
}
// Ownership of remaining pointers:
template<class T, int incr>
PStash<T, incr>::~PStash() {
for(int i = 0; i < next; i++) {
delete storage[i]; // Null pointers OK
storage[i] = 0; // Just to be safe
}
delete []storage;
}
template<class T, int incr>
T* PStash<T, incr>::operator[](int index) const {
require(index >= 0,
"PStash::operator[] index negative");
if(index >= next)
return 0; // To indicate the end
require(storage[index] != 0,
"PStash::operator[] returned null pointer");
// Produce pointer to desired element:
return storage[index];
}
template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
// operator[] performs validity checks:
T* v = operator[](index);
// "Remove" the pointer:
if(v != 0) storage[index] = 0;
return v;
}
template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
const int psz = sizeof(T*);
T** st = new T*[quantity + increase];
memset(st, 0, (quantity + increase) * psz);
memcpy(st, storage, quantity * psz);
quantity += increase;
delete []storage; // Old storage
storage = st; // Point to new memory
}
#endif // TPSTASH_H ///:~
The default increment size used here is
small to guarantee that calls to inflate( ) occur. This way we can
make sure it works correctly.
To test the
ownership control of the templatized PStash, the
following class will report
creations and destructions of
itself, and also guarantee that all objects that have been created were also
destroyed. AutoCounter will allow only objects of its type to be created
on the
stack:
//: C16:AutoCounter.h
#ifndef AUTOCOUNTER_H
#define AUTOCOUNTER_H
#include "../require.h"
#include <iostream>
#include <set> // Standard C++ Library container
#include <string>
class AutoCounter {
static int count;
int id;
class CleanupCheck {
std::set<AutoCounter*> trace;
public:
void add(AutoCounter* ap) {
trace.insert(ap);
}
void remove(AutoCounter* ap) {
require(trace.erase(ap) == 1,
"Attempt to delete AutoCounter twice");
}
~CleanupCheck() {
std::cout << "~CleanupCheck()"<< std::endl;
require(trace.size() == 0,
"All AutoCounter objects not cleaned up");
}
};
static CleanupCheck verifier;
AutoCounter() : id(count++) {
verifier.add(this); // Register itself
std::cout << "created[" << id << "]"
<< std::endl;
}
// Prevent assignment and copy-construction:
AutoCounter(const AutoCounter&);
void operator=(const AutoCounter&);
public:
// You can only create objects with this:
static AutoCounter* create() {
return new AutoCounter();
}
~AutoCounter() {
std::cout << "destroying[" << id
<< "]" << std::endl;
verifier.remove(this);
}
// Print both objects and pointers:
friend std::ostream& operator<<(
std::ostream& os, const AutoCounter& ac){
return os << "AutoCounter " << ac.id;
}
friend std::ostream& operator<<(
std::ostream& os, const AutoCounter* ac){
return os << "AutoCounter " << ac->id;
}
};
#endif // AUTOCOUNTER_H ///:~
The AutoCounter class does two
things. First, it sequentially numbers each instance of AutoCounter: the
value of this number is kept in id, and the number is generated using the
static data member count.
Second, and more complex, a
static instance (called verifier) of
the nested class CleanupCheck keeps track of all of the
AutoCounter objects that are created and destroyed, and reports back to
you if you don’t clean all of them up (i.e. if there is a memory leak).
This behavior is accomplished using a
set
class from the Standard C++ Library, which is a wonderful example of how
well-designed templates can make life easy (you can learn about all the
containers in the Standard C++ Library in Volume 2 of this book, available
online).
The set class is templatized on
the type that it holds; here it is instantiated to hold AutoCounter
pointers. A set will allow only one instance of each distinct object to
be added; in add( ) you can see this take place with the
set::insert( ) function. insert( ) actually informs you
with its return value if you’re trying to add something that’s
already been added; however, since object addresses are being added we can rely
on C++’s guarantee that all objects have unique
addresses.
In remove( ),
set::erase( ) is used to remove an AutoCounter pointer from
the set. The return value tells you how many instances of the element
were removed; in our case we only expect zero or one. If the value is zero,
however, it means this object was already deleted from the set and
you’re trying to delete it a second time, which is a programming error
that will be reported through
require( ).
The destructor for CleanupCheck
does a final check by making sure that the size of the set is zero
– this means that all of the objects have been properly cleaned up. If
it’s not zero, you have a memory leak, which is reported through
require( ).
The constructor and destructor for
AutoCounter register and unregister themselves with the verifier
object. Notice that the constructor, copy-constructor, and assignment operator
are private, so the only way for you to create an object is with the
static create( ) member function – this is a simple example of
a factory, and it
guarantees that all objects are created on the heap, so
verifier will not get confused over assignments and
copy-constructions.
Since all of the member functions have
been inlined, the only reason for the implementation file is to contain the
static data member definitions:
//: C16:AutoCounter.cpp {O}
// Definition of static class members
#include "AutoCounter.h"
AutoCounter::CleanupCheck AutoCounter::verifier;
int AutoCounter::count = 0;
///:~
With AutoCounter in hand, we can
now test the facilities of the PStash. The following example not only
shows that the PStash destructor cleans up all the objects that it
currently owns, but it also demonstrates how the AutoCounter class
detects objects that haven’t been cleaned up:
//: C16:TPStashTest.cpp
//{L} AutoCounter
#include "AutoCounter.h"
#include "TPStash.h"
#include <iostream>
#include <fstream>
using namespace std;
int main() {
PStash<AutoCounter> acStash;
for(int i = 0; i < 10; i++)
acStash.add(AutoCounter::create());
cout << "Removing 5 manually:" << endl;
for(int j = 0; j < 5; j++)
delete acStash.remove(j);
cout << "Remove two without deleting them:"
<< endl;
// ... to generate the cleanup error message.
cout << acStash.remove(5) << endl;
cout << acStash.remove(6) << endl;
cout << "The destructor cleans up the rest:"
<< endl;
// Repeat the test from earlier chapters:
ifstream in("TPStashTest.cpp");
assure(in, "TPStashTest.cpp");
PStash<string> stringStash;
string line;
while(getline(in, line))
stringStash.add(new string(line));
// Print out the strings:
for(int u = 0; stringStash[u]; u++)
cout << "stringStash[" << u << "] = "
<< *stringStash[u] << endl;
} ///:~
When AutoCounter elements 5 and 6
are removed from the PStash, they become the responsibility of the
caller, but since the caller never cleans them up they cause memory leaks, which
are then detected by AutoCounter at run time.
When you run the program, you’ll
see that the error message isn’t as specific as it could be. If you use
the scheme presented in AutoCounter to discover memory leaks in your own
system, you will probably want to have it print out more detailed information
about the objects that haven’t been cleaned up. Volume 2 of this book
shows more sophisticated ways to do
this.
Turning ownership on and off
Let’s return to the ownership
problem. Containers that hold
objects by value don’t usually worry about ownership because they clearly
own the objects they contain. But if your container holds pointers (which is
more common with C++, especially with polymorphism),
then it’s very likely those pointers may also be used somewhere else in
the program, and you don’t necessarily want to delete the object because
then the other pointers in the program would be referencing a destroyed object.
To prevent this from happening, you must consider ownership when designing and
using a container.
Many programs are much simpler than this,
and don’t encounter the ownership problem: One container holds pointers to
objects that are used only by that container. In this case ownership is very
straightforward: The container owns its objects.
The best approach to handling the
ownership problem is to give the client programmer a choice. This is often
accomplished by a constructor argument that defaults to indicating ownership
(the simplest case). In addition there may be “get” and
“set” functions to view and modify the ownership of the container.
If the container has functions to remove an object, the ownership state usually
affects that removal, so you may also find options to control destruction in the
removal function. You could conceivably add ownership data for every element in
the container, so each position would know whether it needed to be destroyed;
this is a variant of reference counting, except that
the container and not the object knows the number of references pointing to an
object.
//: C16:OwnerStack.h
// Stack with runtime conrollable ownership
#ifndef OWNERSTACK_H
#define OWNERSTACK_H
template<class T> class Stack {
struct Link {
T* data;
Link* next;
Link(T* dat, Link* nxt)
: data(dat), next(nxt) {}
}* head;
bool own;
public:
Stack(bool own = true) : head(0), own(own) {}
~Stack();
void push(T* dat) {
head = new Link(dat,head);
}
T* peek() const {
return head ? head->data : 0;
}
T* pop();
bool owns() const { return own; }
void owns(bool newownership) {
own = newownership;
}
// Auto-type conversion: true if not empty:
operator bool() const { return head != 0; }
};
template<class T> T* Stack<T>::pop() {
if(head == 0) return 0;
T* result = head->data;
Link* oldHead = head;
head = head->next;
delete oldHead;
return result;
}
template<class T> Stack<T>::~Stack() {
if(!own) return;
while(head)
delete pop();
}
#endif // OWNERSTACK_H ///:~
The default behavior is for the container
to destroy its objects but you can change this by either modifying the
constructor argument or using the owns( ) read/write member
functions.
As with most templates you’re
likely to see, the entire implementation is contained in the header file.
Here’s a small test that exercises the ownership
abilities:
//: C16:OwnerStackTest.cpp
//{L} AutoCounter
#include "AutoCounter.h"
#include "OwnerStack.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() {
Stack<AutoCounter> ac; // Ownership on
Stack<AutoCounter> ac2(false); // Turn it off
AutoCounter* ap;
for(int i = 0; i < 10; i++) {
ap = AutoCounter::create();
ac.push(ap);
if(i % 2 == 0)
ac2.push(ap);
}
while(ac2)
cout << ac2.pop() << endl;
// No destruction necessary since
// ac "owns" all the objects
} ///:~
The ac2 object doesn’t own
the objects you put into it, thus ac is the “master”
container which takes responsibility for ownership. If, partway through the
lifetime of a container, you want to change whether a container owns its
objects, you can do so using owns( ).
It would also be possible to change the
granularity of the ownership so that it is on an object-by-object basis, but
that will probably make the solution to the ownership problem more complex than
the
problem.
Holding objects by value
Actually creating a copy of the objects
inside a generic container is a complex problem if you don’t have
templates. With templates, things are relatively simple – you just say
that you are holding objects rather than pointers:
//: C16:ValueStack.h
// Holding objects by value in a Stack
#ifndef VALUESTACK_H
#define VALUESTACK_H
#include "../require.h"
template<class T, int ssize = 100>
class Stack {
// Default constructor performs object
// initialization for each element in array:
T stack[ssize];
int top;
public:
Stack() : top(0) {}
// Copy-constructor copies object into array:
void push(const T& x) {
require(top < ssize, "Too many push()es");
stack[top++] = x;
}
T peek() const { return stack[top]; }
// Object still exists when you pop it;
// it just isn't available anymore:
T pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
};
#endif // VALUESTACK_H ///:~
The copy constructor for the contained
objects does most of the work by passing and returning the objects by value.
Inside push( ), storage of the object onto the Stack array is
accomplished with T::operator=. To guarantee that it works, a class
called SelfCounter keeps track of object creations and
copy-constructions:
//: C16:SelfCounter.h
#ifndef SELFCOUNTER_H
#define SELFCOUNTER_H
#include "ValueStack.h"
#include <iostream>
class SelfCounter {
static int counter;
int id;
public:
SelfCounter() : id(counter++) {
std::cout << "Created: " << id << std::endl;
}
SelfCounter(const SelfCounter& rv) : id(rv.id){
std::cout << "Copied: " << id << std::endl;
}
SelfCounter operator=(const SelfCounter& rv) {
std::cout << "Assigned " << rv.id << " to "
<< id << std::endl;
return *this;
}
~SelfCounter() {
std::cout << "Destroyed: "<< id << std::endl;
}
friend std::ostream& operator<<(
std::ostream& os, const SelfCounter& sc){
return os << "SelfCounter: " << sc.id;
}
};
#endif // SELFCOUNTER_H ///:~
//: C16:SelfCounter.cpp {O}
#include "SelfCounter.h"
int SelfCounter::counter = 0; ///:~
//: C16:ValueStackTest.cpp
//{L} SelfCounter
#include "ValueStack.h"
#include "SelfCounter.h"
#include <iostream>
using namespace std;
int main() {
Stack<SelfCounter> sc;
for(int i = 0; i < 10; i++)
sc.push(SelfCounter());
// OK to peek(), result is a temporary:
cout << sc.peek() << endl;
for(int k = 0; k < 10; k++)
cout << sc.pop() << endl;
} ///:~
When a Stack container is created,
the default constructor of the contained object is called for each object in the
array. You’ll initially see 100 SelfCounter objects created for no
apparent reason, but this is just the array initialization. This can be a bit
expensive, but there’s no way around it in a simple design like this. An
even more complex situation arises if you make the Stack more general by
allowing the size to grow dynamically, because in the implementation shown above
this would involve creating a new (larger) array, copying the old array to the
new, and destroying the old array (this is, in fact, what the Standard C++
Library vector class does).
 |
|
|
