MFC Programmer's SourceBook : Thinking in C++

Stack with constructors & destructors

Reimplementing the linked list (inside Stack) with constructors and destructors shows up a significant problem. Here’s the modified header file:

//: C06:Stack3.h
// With constructors/destructors
#ifndef STACK3_H
#define STACK3_H

class Stack {
  struct Link {
    void* data;
    Link* next;
    void initialize(void* Data, Link* Next);
  } * head;
public:
  Stack();
  ~Stack();
  void push(void* Data);
  void* peek();
  void* pop();
};
#endif // STACK3_H ///:~

Notice that although Stack has a constructor and destructor, the nested class Link does not. This has nothing to do with the fact that it’s nested. The problem arises when it is used:

//: C06:Stack3.cpp {O}
// Constructors/destructors
#include <cstdlib>
#include "../require.h"
#include "Stack3.h"
using namespace std;

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

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

void Stack::push(void* Data) {
  // Can't use a constructor with malloc!
  Link* newLink = (Link*)malloc(sizeof(Link));
  require(newLink);
  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;
}

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

Link is created inside Stack::push, but it’s created on the heap and there’s the rub. How do you create an object on the heap if it has a constructor? So far we’ve been saying, “OK, here’s a piece of memory on the heap and I want you to pretend that it’s actually a real object.” But the constructor doesn’t allow us to hand it a memory address upon which it will build an object. [25] The creation of an object is critical, and the C++ constructor wants to be in control of the whole process to keep things safe. There is an easy solution to this problem, the operator new, that we’ll look at in Chapter 11, but for now the C approach to dynamic allocation will have to suffice. Because the allocation and cleanup are hidden within Stack – it’s part of the underlying implementation – you don’t see the effect in the test program:

//: C06:Stktst3.cpp
//{L} Stack3
// Constructors/destructors
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include "../require.h"
#include "Stack3.h"
using namespace std;

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

The constructor and destructor for textlines are called automatically, so the user of the class can focus on what to do with the object and not worry about whether or not it will be properly initialized and cleaned up.

[25]Actually, there's a syntax that does allow you to do this. But it's for special cases and doesn't solve the general problem described here.