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 very 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();
};
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 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. (If you
pop( )
an element, then
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. cleanup( )
goes through the
Stack
and removes each element
and
frees the
data
pointer (thus the
data
objects
must
be on the heap). Notice there’s something you have to keep track of, a
bit: if you
pop( )
the element, you must call
delete,
but if you don’t, then
cleanup( )
will call
delete.
The subject of “who’s responsible for the memory” is not even
that simple, as we’ll see in later chapters.
Here
are the definitions for the member functions:
//: C04:Nested.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() { 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() {
Link* cursor = head;
while(head) {
cursor = cursor->next;
delete head->data; // Assumes a 'new'!
delete head;
head = cursor;
}
head = 0; // Officially 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.
Stack::cleanup( )
creates a
cursor
to move through the
Stack
and
delete
both the
data
in each link and the link itself. After it’s finished destroying all the
links,
head
is set to zero. This not only indicates that the
Stack
is empty, but if
cleanup( )
is called a second time it will not wander off and try to
delete
inappropriate storage (which would be a run-time error, and might cause
difficult-to-find bugs).
Here’s
an example to test the
Stack:
//: C04:StackTest.cpp
//{L} Nested
//{T} NestTest.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 very 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.
Global
scope resolution
The
scope resolution operator gets you out of situations where the name the
compiler chooses by default (the “nearest” name) isn’t what
you want. For example, suppose you have a structure with a local identifier
a,
and you want to select a global identifier
a
from inside a member function. The compiler would default to choosing the local
one, so you must tell it to do otherwise. When you want to specify a global
name using scope resolution, you use the operator with nothing in front of it.
Here’s an example that shows global scope resolution for both a variable
and a function:
//: C04:Scoperes.cpp
// Global scope resolution
int a;
void f() {}
struct S {
int a;
void f();
};
void S::f() {
::f(); // Would be recursive otherwise!
::a++; // Select the global a
a--; // The a at struct scope
}
int
main() { S s; f(); } ///:~
Without
scope resolution in
S::f( ),
the compiler would default to selecting the member versions of
f( )
and
A.
Contact: webmaster@codeguru.com
CodeGuru - the website for developers.