Nested structures
The convenience of taking data and
function names out of the global name space extends to structures. You can nest
a structure within another structure, and therefore keep associated elements
together. The declaration syntax is what you would expect, as you can see in the
following structure, which implements a push-down stack as a simple linked list
so it “never” runs
out of memory:
//: C04:Stack.h
// Nested struct in linked list
#ifndef STACK_H
#define STACK_H
struct Stack {
struct Link {
void* data;
Link* next;
void initialize(void* dat, Link* nxt);
}* head;
void initialize();
void push(void* dat);
void* peek();
void* pop();
void cleanup();
};
#endif // STACK_H ///:~
The nested struct is called
Link, and it contains a pointer to the next Link in the list and a
pointer to the data stored in the Link. If the next pointer is
zero, it means you’re at the end of the list.
Notice that the head pointer is
defined right after the declaration for struct Link, instead of a
separate definition Link* head. This is a syntax that came from C, but it
emphasizes the importance of the semicolon after the structure declaration; the
semicolon indicates the end of the comma-separated list of definitions of that
structure type. (Usually the list is empty.)
The nested structure has its own
initialize( ) function, like all the structures presented so far, to
ensure proper initialization. Stack has both an initialize( )
and cleanup( ) function, as well as push( ), which takes
a pointer to the data you wish to store (it assumes this has been allocated on
the heap), and pop( ), which returns the data pointer from
the top of the Stack and removes the top element. (When you
pop( ) an element, you are responsible for destroying the object
pointed to by the data.) The peek( ) function also returns
the data pointer from the top element, but it leaves the top element on
the Stack.
Here are the definitions for the member
functions:
//: C04:Stack.cpp {O}
// Linked list with nesting
#include "Stack.h"
#include "../require.h"
using namespace std;
void
Stack::Link::initialize(void* dat, Link* nxt) {
data = dat;
next = nxt;
}
void Stack::initialize() { head = 0; }
void Stack::push(void* dat) {
Link* newLink = new Link;
newLink->initialize(dat, head);
head = newLink;
}
void* Stack::peek() {
require(head != 0, "Stack empty");
return head->data;
}
void* Stack::pop() {
if(head == 0) return 0;
void* result = head->data;
Link* oldHead = head;
head = head->next;
delete oldHead;
return result;
}
void Stack::cleanup() {
require(head == 0, "Stack not empty");
} ///:~
The first definition is particularly
interesting because it shows you how to define a member of a nested structure.
You simply use an additional level of scope resolution to specify the name of
the enclosing struct. Stack::Link::initialize( ) takes the
arguments and assigns them to its members.
Stack::initialize( ) sets
head to zero, so the object knows it has an empty list.
Stack::push( ) takes the
argument, which is a pointer to the variable you want to keep track of, and
pushes it on the Stack. First, it uses new to allocate storage for
the Link it will insert at the top. Then it calls Link’s
initialize( ) function to assign the appropriate values to the
members of the Link. Notice that the next pointer is assigned to
the current head; then head is assigned to the new Link
pointer. This effectively pushes the Link in at the top of the
list.
Stack::pop( ) captures the
data pointer at the current top of the Stack; then it moves the
head pointer down and deletes the old top of the Stack, finally
returning the captured pointer. When pop( ) removes the last
element, then head again becomes zero, meaning the Stack is
empty.
Stack::cleanup( )
doesn’t actually do any cleanup. Instead, it establishes a firm policy
that “you (the client programmer using this Stack object) are
responsible for popping all the elements off this Stack and deleting
them.” The require( ) is used to indicate that a programming
error has occurred if the Stack is not empty.
Why couldn’t the Stack
destructor be responsible for all the objects that the client programmer
didn’t pop( )? The problem is that the Stack is holding
void pointers, and you’ll learn in Chapter 13 that calling
delete for a void* doesn’t clean things up properly. The
subject of “who’s responsible for the memory” is not even
that simple, as we’ll see in later chapters.
Here’s an example to test the
Stack:
//: C04:StackTest.cpp
//{L} Stack
//{T} StackTest.cpp
// Test of nested linked list
#include "Stack.h"
#include "../require.h"
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[]) {
requireArgs(argc, 1); // File name is argument
ifstream in(argv[1]);
assure(in, argv[1]);
Stack textlines;
textlines.initialize();
string line;
// Read file and store lines in the Stack:
while(getline(in, line))
textlines.push(new string(line));
// Pop the lines from the Stack and print them:
string* s;
while((s = (string*)textlines.pop()) != 0) {
cout << *s << endl;
delete s;
}
textlines.cleanup();
} ///:~
This is similar to the earlier example,
but it pushes lines from a file (as string pointers) on the
Stack and then pops them off, which results in the file being printed out
in reverse order. Note that the pop( ) member function returns a
void* and this must be cast back to a string* before it can be
used. To print the string, the pointer is dereferenced.
As textlines is being filled, the
contents of line is “cloned” for each push( ) by
making a new string(line). The value returned from the new-expression is
a pointer to the new string that was created and that copied the
information from line. If you had simply passed the address of
line to push( ), you would end up with a Stack filled
with identical addresses, all pointing to line. You’ll learn more
about this “cloning” process later in the book.
The file name is taken from the command
line. To guarantee that there are enough arguments on
the command line, you see a second function used from the
require.h header file:
requireArgs( ), which compares argc
to the desired number of arguments and prints an appropriate error message and
exits the program if there aren’t enough
arguments.
