MFC Programmer's SourceBook : Thinking in C++

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:Nested.h
// Nested struct in linked list
#ifndef NESTED_H
#define NESTED_H

struct Stack {
  struct Link {
    void* data;
    Link* next;
    void initialize(void* Data, Link* Next);
  } * head;
  void initialize();
  void push(void* Data);
  void* peek();
  void* pop();
  void cleanup();
};
#endif // NESTED_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 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 (assumed to have been allocated on the heap), and pop( ), which returns the data pointer from the top of the Stack and removes the top element. (Notice that you are responsible for destroying the destination of the data pointer.) 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 (so it must be on the heap).

Here are the definitions for the member functions:

//: C04:Nested.cpp {O}
// Linked list with nesting
#include <cstdlib>
#include "../require.h"
#include "Nested.h"
using namespace std;

void Stack::Link::initialize(
    void* Data, Link* Next) {
  data = Data;
  next = Next;
}

void Stack::initialize() { head = 0; }

void Stack::push(void* Data) {
  Link* newLink = (Link*)malloc(sizeof(Link));
  require(newLink != 0);
  newLink->initialize(Data, 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;
  free(oldHead);
  return result;
}

void Stack::cleanup() {
  Link* cursor = head;
  while(head) {
    cursor = cursor->next;
    free(head->data); // Assumes a malloc!
    free(head);
    head = cursor;
  }
} ///:~

The first definition is particularly interesting because it shows you how to define a member of a nested structure. You simply use the scope resolution operator a second time, to specify the name of the enclosing struct. The Stack::Link::initialize( ) function takes the arguments and assigns them to its members. Although you can certainly do these things by hand quite easily, you’ll see a different form of this function in the future, so it will make much more sense.

The Stack::initialize( ) function sets head to zero, so the object knows it has an empty list.

Stack::push( ) takes the argument, a pointer to the variable you want to keep track of using the Stack, and pushes it on the Stack. First, it uses malloc( ) to allocate storage for the Link it will insert at the top. Then it calls the 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( ) stores 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. Stack::cleanup( ) creates a cursor to move through the Stack and free( ) both the data in each link and the link itself.

Here’s an example to test the Stack:

//: C04:NestTest.cpp
//{L} Nested
//{T} NestTest.cpp
// Test of nested linked list
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include "../require.h"
#include "Nested.h"
using namespace std;

int main(int argc, char* argv[]) {
  Stack textlines;
  FILE* file;
  char* s;
  #define BUFSIZE 100
  char buf[BUFSIZE];
  requireArgs(argc, 1); // File name is argument
  textlines.initialize();
  file = fopen(argv[1], "r");
  require(file != 0);
  // Read file and store lines in the Stack:
  while(fgets(buf, BUFSIZE, file)) {
    char* string =(char*)malloc(strlen(buf)+1);
    require(string != 0);
    strcpy(string, buf);
    textlines.push(string);
  }
  // Pop the lines from the Stack and print them:
  while((s = (char*)textlines.pop()) != 0) {
    printf("%s", s); free(s); }
  textlines.cleanup();
} ///:~

This is very similar to the earlier example, but it pushes the lines on the Stack and then pops them off, which results in the file being printed out in reverse order. In addition, the file name is taken from the command line.

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 {O}
// 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
}
///:~

Without scope resolution in S::f( ), the compiler would default to selecting the member versions of f( ) and A.

Contents | Prev | Next