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.
Heap-only
string class
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 14.
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?) To solve this problem in the following version of a simple
String
class,
steps have been taken to prevent the creation of a
String
anywhere but on the heap:
//: C13:Strings.h
// Simple string class
// Can only be built on the heap
#ifndef STRINGS_H
#define STRINGS_H
#include <cstring>
#include <iostream>
class String {
char* s;
String(const char* S) {
s = new char[strlen(S) + 1];
std::strcpy(s, S);
}
// Prevent copying:
String(const String&);
void operator=(String&);
public:
// Only make Strings on the heap:
friend String* makeString(const char* S) {
return new String(S);
}
// Alternate approach:
static String* make(const char* S) {
return new String(S);
}
~String() { delete s; }
operator char*() const { return s;}
char* str() const { return s; }
friend std::ostream&
operator<<(std::ostream& os, const String& S) {
return os << S.s;
}
};
#endif // STRINGS_H ///:~ To
restrict what the user can do with this class, the main constructor is made
private,
so no one can use it but you. In addition, the copy-constructor
is declared
private
but never defined, because you want to prevent anyone from using it, and the
same goes for the
operator=.
The only way for the user to create an object is to call a special function
that creates a
String
on the heap (so you know all
String
objects are created on the heap) and returns its pointer.
There
are two approaches to this function. For ease of use, it can be a global
friend
function (called
makeString( )),
but if you don’t want to pollute the global name space, you can make it a
static
member function (called
make( ))
and
call it by saying
String::make( ).
The latter form has the benefit of more explicitly belonging to the class.
In
the constructor, note the expression:
s
= new char[strlen(S) + 1];
The
square brackets mean that an array of objects is being created (in this case,
an array of
char),
and the number inside the brackets is the number of objects to create. This is
how you create an array at run-time.
The
automatic type conversion to
char*
means that you can use a
String
object anywhere you need a
char*.
In addition, an iostream output operator extends the iostream library to handle
String
objects.
Stash
for pointers
This
version of the
Stash
class, which you last saw in Chapter 4, is changed to reflect all the new
material introduced since Chapter 4. In addition, the new
PStash
holds
pointers
to objects that exist by themselves on the heap, whereas the old
Stash
in Chapter 4 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; }
};
#endif // PSTASH_H ///:~ 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*);
// realloc() is cleaner than this:
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 actually more complicated and less efficient than in the earlier
version. This is because
realloc( ),
which was used before, can resize an existing chunk of memory, or failing that,
automatically copy the contents of your old chunk to a bigger piece. In either
event you don’t have to worry about it,
and
it’s potentially faster if memory doesn’t have to be moved.
There’s no equivalent of
realloc( )
with
new,
however, so in this example you always have to allocate a bigger chunk, perform
a copy, and delete the old chunk. In this situation it might make sense to use
malloc( ),
realloc( ),
and
free( )
in the underlying implementation rather than
new
and
delete.
Fortunately, the implementation is hidden so the client programmer will remain
blissfully ignorant of these kinds of changes; also the
malloc( )
family of functions is guaranteed to interact safely in parallel with
new
and
delete,
as long as you don’t mix calls with the same chunk of memory, so this is
a completely plausible thing to do.
A
test
Here’s
the old test program for
Stash
rewritten for the
PStash:
//: C13:Pstest.cpp
//{L} PStash
// Test of pointer Stash
#include <iostream>
#include <fstream>
#include "../require.h"
#include "PStash.h"
#include "Strings.h"
using namespace std;
int main() {
PStash intStash;
// new works with built-in types, too:
for(int i = 0; i < 25; i++)
intStash.add(new int(i)); // Pseudo-constr.
for(int u = 0; u < intStash.count(); u++)
cout << "intStash[" << u << "] = "
<< *(int*)intStash[u] << endl;
ifstream infile("Pstest.cpp");
assure(infile, "Pstest.cpp");
const int bufsize = 80;
char buf[bufsize];
PStash stringStash;
// Use global function makeString:
for(int j = 0; j < 10; j++)
if(infile.getline(buf, bufsize))
stringStash.add(makeString(buf));
// Use static member make:
while(infile.getline(buf, bufsize))
stringStash.add(String::make(buf));
// Print out the strings:
for(int v = 0; stringStash[v]; v++) {
char* p = *(String*)stringStash[v];
cout << "stringStash[" << v << "] = "
<< p << 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 into another
PStash,
converting each line into a
String
object. You can see that both
makeString( )
and
String::make( )
are
used to show the difference between the two. The
static
member is probably the better approach because it’s more explicit.
When
fetching the pointers back out, you see the expression:
char*
p = *(String*)stringStash[i];
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 when it wants a
char*,
so it calls the automatic type conversion operator in
String
to produce a
char*. 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 3. Here’s the new
header file:
//: C13:Stack11.h
// New version of Stack
#ifndef STACK11_H
#define STACK11_H
class Stack {
struct Link {
void* data;
Link* next;
Link(void* Data, Link* Next) {
data = Data;
next = Next;
}
} * head;
public:
Stack() { head = 0; }
~Stack();
void push(void* Data) {
head = new Link(Data,head);
}
void* peek() const { return head->data; }
void* pop();
};
#endif // STACK11_H ///:~ The
nested
struct
Link
can now have its own constructor because in
Stack::push( )
the use of
new
safely calls that constructor. (And notice how much cleaner the syntax is,
which reduces potential bugs.) The
Link::Link( )
constructor simply initializes the
data
and
next
pointers, so in
Stack::push( )
the line
head
= new Link(Data,head);
not
only allocates a new link, but neatly initializes the pointers for that link.
The
rest of the logic is virtually identical to what it was in Chapter 3. Here is
the implementation of the two remaining (non-inline) functions:
//: C13:Stack11.cpp {O}
// New version of Stack
#include "Stack11.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
Stack,
so again there is the possibility of an undesirable memory leak if the user
doesn’t take responsibility for the pointers in the
Stack.
You can see this in the test program:
//: C13:Stktst11.cpp
//{L} Stack11
// Test new Stack
#include <iostream>
#include <fstream>
#include "../require.h"
#include "Stack11.h"
#include "Strings.h"
using namespace std;
int main() {
// Could also use command-line argument:
ifstream file("Stktst11.cpp");
assure(file, "Stktst11.cpp");
const int bufsize = 100;
char buf[bufsize];
Stack textlines;
// Read file and store lines in the Stack:
while(file.getline(buf,bufsize))
textlines.push(String::make(buf));
// 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 turned into a
String
object, which is stored in a
Stack
and then printed. This program doesn’t
delete
the pointers in the
Stack
and the
Stack
itself doesn’t do it, so that memory is lost.
Go to CodeGuru.com
Contact: webmaster@codeguru.com
© Copyright 1997-1999 CodeGuru