Early
examples redesigned
Now
that
new
and
delete
have been introduced (as well as many other subjects), the
Stash
and
Stack
examples
from the early part of this book can be rewritten using all the features
discussed in the book so far. Examining the new code will also give you a
useful review of the topics.
At
this point in the book, neither the
Stash
nor
Stack
classes will “own”
the objects they point to; that is, when the
Stash
or
Stack
object goes out of scope, it will not call
delete
for all the objects it points to. The reason this is not possible is because,
in an attempt to be generic, they hold
void
pointers.
If you
delete
a
void
pointer, the only thing that happens is the memory gets released, because
there’s no type information and no way for the compiler to know what
destructor to call. When a pointer is returned from the
Stash
or
Stack
object, you must cast it to the proper type before using it. These problems
will be dealt with in the next chapter [[??]], and in Chapter XX.
Because
the container doesn’t own the pointer, the user must be responsible for
it. This means there’s a serious problem if you add pointers to objects
created on the stack
and
objects
created on the heap to the same container because a delete-expression is unsafe
for a pointer that hasn’t been allocated on the heap. (And when you fetch
a pointer back from the container, how will you know where its object has been
allocated?). Thus, you must be sure that objects stored in the upcoming
versions of
Stash
and
Stack
are
only made on the heap, either through careful programming or by creating
classes that can only be built on the heap.
Stash
for pointers
This
version of the
Stash
class, which you last saw in Chapter XX, is changed to reflect all the new
material introduced since Chapter XX. In addition, the new
PStash
holds
pointers
to objects that exist by themselves on the heap, whereas the old
Stash
in Chapter XX and earlier copied the
objects
into the
Stash
container. With the introduction of
new
and
delete,
it’s easy and safe to hold pointers to objects that have been created on
the heap.
Here’s
the header file for the “pointer
Stash”:
//: C13:PStash.h
// Holds pointers instead of objects
#ifndef PSTASH_H
#define PSTASH_H
class PStash {
int quantity; // Number of storage spaces
int next; // Next empty space
// Pointer storage:
void** storage;
void inflate(int increase);
public:
PStash() {
quantity = 0;
storage = 0;
next = 0;
}
// No ownership:
~PStash() { delete []storage; }
int add(void* element);
void* operator[](int index) const; // Fetch
// Number of elements in Stash:
int count() const { return next; }
};
The
underlying data elements are fairly similar, but now
storage
is an array of
void
pointers,
and the allocation of storage for that array is performed with
new
instead of
malloc( ).
In the expression
void**
st = new void*[quantity + increase];
the
type of object allocated is a
void*,
so the expression allocates an array of
void
pointers.
The
destructor deletes the storage where the
void
pointers are held, rather than attempting to delete what they point at (which,
as previously noted, will release their storage and not call the destructors
because a
void
pointer
has no type information).
The
other change is the replacement of the
fetch( )
function with
operator[
],
which makes more sense syntactically. Again, however, a
void*
is returned, so the user must remember what types are stored in the container
and cast the pointers when fetching them out (a problem which will be repaired
in future chapters).
Here
are the member function definitions:
//: C13:PStash.cpp {O}
// Pointer Stash definitions
#include "PStash.h"
#include <iostream>
#include <cstring> // 'mem' functions
using namespace std;
int PStash::add(void* element) {
const int inflateSize = 10;
if(next >= quantity)
inflate(inflateSize);
storage[next++] = element;
return(next - 1); // Index number
}
// Operator overloading replacement for fetch
void* PStash::operator[](int index) const {
if(index >= next || index < 0)
return 0; // Out of bounds
// Produce pointer to desired element:
return storage[index];
}
void PStash::inflate(int increase) {
const int psz = sizeof(void*);
void** st = new void*[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
The
add( )
function is effectively the same as before, except that the pointer is stored
instead of a copy of the whole object, which, as you’ve seen, actually
requires a copy-constructor for normal objects.
The
inflate( )
code is modified to handle the allocation of an array of
void*
instead of the previous design which was only working with raw bytes. Here,
instead of using the prior approach of copying by array indexing, the Standard
C library function
memset( )
is first used to set all the new memory to zero (this is not strictly
necessary, since the
PStash
is presumably managing all the memory correctly – but it usually
doesn’t hurt to throw in a bit of extra care). Then
memcpy( )
moves the existing data from the old location to the new. Often, functions like
memset( )
and
memcpy( )
have been optimized over time and so they may be faster than the loops shown
previously, but in a function like
inflate( )
that
will probably not be used that often you probably won’t see a performance
difference. However, the fact that the function calls are more concise than the
loops may help prevent coding errors.
A
test
Here’s
the old test program for
Stash
rewritten for the
PStash:
//: C13:PStashTest.cpp
//{L} PStash
// Test of pointer Stash
#include "PStash.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() {
PStash intStash;
// 'new' works with built-in types, too. Note
// the "pseudo-constructor" syntax:
for(int i = 0; i < 25; i++)
intStash.add(new int(i));
for(int u = 0; u < intStash.count(); u++)
cout << "intStash[" << u << "] = "
<< *(int*)intStash[u] << endl;
ifstream infile("PStashTest.cpp");
assure(infile, "PStashTest.cpp");
PStash stringStash;
string line;
while(getline(infile, line))
stringStash.add(new string(line));
// Print out the strings:
for(int v = 0; stringStash[v]; v++)
cout << "stringStash[" << v << "] = "
<< *(string*)stringStash[v] << endl;
As
before,
Stashes
are created and filled with information, but this time the information is the
pointers resulting from new-expressions. In the first case, note the line:
intStash.add(new
int(i));
The
expression
new
int(i)
uses the pseudoconstructor form,
so storage for a new
int
object is created on the heap, and the
int
is initialized to the value
i. Note
that during printing, the value returned by
PStash::operator[
]
must be cast to the proper type; this is repeated for the rest of the
PStash
objects in the program. It’s an undesirable effect of using
void
pointers as
the underlying representation and will be fixed in later chapters.
The
second test opens the source code file and reads it one line at a time into
another
PStash.
Each line is read into a
string
using
getline( ),
then a
new
string
is created from
line
to make an independent copy of that line. If we just passed in the address of
line
each
time, we’d get a whole bunch of pointers pointing to
line,
which itself would only contain the last line that was read from the file.
When
fetching the pointers back out, you see the expression:
The
pointer returned from
operator[
]
must be cast to a
string*
to give it the proper type. Then the
string*
is dereferenced so the expression evaluates to an object, at which point the
compiler sees a
string
object to send to
cout. In
this example, the objects created on the heap are never destroyed. This is not
harmful here because the storage is released when the program ends, but
it’s not something you want to do in practice. It will be fixed in later
chapters.
The
stack
The
Stack
benefits
greatly from all the features introduced since Chapter XX. [[ I think at this
point only inlines have been added??]] Here’s the new header file:
//: C13:Stack4.h
// New version of Stack
#ifndef STACK4_H
#define STACK4_H
class Stack {
struct Link {
void* data;
Link* next;
Link(void* dat, Link* nxt) {
data = dat;
next = nxt;
}
}* head;
public:
Stack() { head = 0; }
~Stack();
void push(void* dat) {
head = new Link(dat,head);
}
void* peek() const { return head->data; }
void* pop();
};
The
rest of the logic is virtually identical to what it was in Chapter XX. Here is
the implementation of the two remaining (non-inline) functions:
//: C13:Stack4.cpp {O}
// New version of Stack
#include "Stack4.h"
void* Stack::pop() {
if(head == 0) return 0;
void* result = head->data;
Link* oldHead = head;
head = head->next;
delete oldHead;
return result;
}
Stack::~Stack() {
Link* cursor = head;
while(head) {
cursor = cursor->next;
delete head;
head = cursor;
}
The
only difference is the use of
delete
instead of
free( )
in the destructor.
As
with the
Stash,
the use of
void
pointers means that the objects created on the heap cannot be destroyed by the
Stack4,
so again there is the possibility of an undesirable memory leak if the user
doesn’t take responsibility for the pointers in the
Stack4.
You can see this in the test program:
//: C13:Stack4Test.cpp
//{L} Stack4
// Test new Stack
#include "Stack4.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() {
// Could also use command-line argument:
ifstream file("Stack4Test.cpp");
assure(file, " Stack4Test.cpp");
Stack textlines;
string line;
while(getline(file, line))
textlines.push(new string(line));
// Pop lines from the Stack and print them:
string* s;
while((s = (string*)textlines.pop()) != 0)
cout << *s << endl;
As
with the
Stash
example, a file is opened and each line is read into a
string
object, which is duplicated via
new
as
it is stored in a
Stack.
This program doesn’t
delete
the pointers in the
Stack
and the
Stack
itself doesn’t do it, so that memory is lost.
Contact: webmaster@codeguru.com
CodeGuru - the website for developers.