MFC Programmer's SourceBook : Thinking in C++

Bruce Eckel's Thinking in C++, 2nd Ed Contents | Prev | Next

Stash and stack
as templates

It turns out that the Stash and Stack classes that have been updated periodically throughout this book are actually container classes, so it makes sense to convert them to templates. But first, one other important issue arises with container classes: When a container releases a pointer to an object, does it destroy that object? For example, when a container object goes out of scope, does it destroy all the objects it points to?

The ownership problem

This issue is commonly referred to as ownership . Containers that hold entire objects don’t usually worry about ownership because they clearly own the objects they contain. But if your container holds pointers (which is more common with C++, especially with polymorphism), then it’s very likely those pointers may also be used somewhere else in the program, and you don’t necessarily want to delete the object because then the other pointers in the program would be referencing a destroyed object. To prevent this from happening, you must consider ownership when designing and using a container.

Many programs are very simple, and one container holds pointers to objects that are used only by that container. In this case ownership is very straightforward: The container owns its objects. Generally, you’ll want this to be the default case for a container because it’s the most common situation.

The best approach to handling the ownership problem is to give the client programmer the choice. This is often accomplished by a constructor argument that defaults to indicating ownership (typically desired for simple programs). In addition there may be read and set functions to view and modify the ownership of the container. If the container has functions to remove an object, the ownership state usually affects that removal, so you may also find options to control destruction in the removal function. You could conceivably also add ownership data for every element in the container, so each position would know whether it needed to be destroyed; this is a variant of reference counting where the container and not the object knows the number of references pointing to an object.

Stash as a template

The “stash” class that has been evolving throughout the book (last seen in Chapter XX) is an ideal candidate for a template. Now an iterator has been added along with ownership operations:

//: C16:TStash.h
// PSTASH using templates
#ifndef TSTASH_H
#define TSTASH_H
#include "../require.h"
#include <cstdlib>

// More convenient than nesting in TStash:
enum Owns { no = 0, yes = 1, Default };
// Declaration required:
template<class Type, int sz> class TStashIter;

template<class Type, int chunksize = 20>
class TStash {
  int quantity;
  int next;
  Owns _owns; // Flag
  void inflate(int increase = chunksize);
protected:
  Type** storage;
public:
  TStash(Owns owns = yes);
  ~TStash();
  Owns owns() const { return _owns; }
  void owns(Owns newOwns) { _owns = newOwns; }
  int add(Type* element);
  int remove(int index, Owns d = Default);
  Type* operator[](int index);
  int count() const { return next; }
  friend class TStashIter<Type, chunksize>;
};

template<class Type, int sz = 20>
class TStashIter {
  TStash<Type, sz>& ts;
  int index;
public:
  TStashIter(TStash<Type, sz>& TS)
    : ts(TS), index(0) {}
  TStashIter(const TStashIter& rv)
    : ts(rv.ts), index(rv.index) {}
  // Jump interator forward or backward:
  void forward(int amount) {
    index += amount;
    if(index >= ts.next) index = ts.next -1;
  }
  void backward(int amount) {
    index -= amount;
    if(index < 0) index = 0;
  }
  // Return value of ++ and -- to be
  // used inside conditionals:
  int operator++() {
    if(++index >= ts.next) return 0;
    return 1;
  }
  int operator++(int) { return operator++(); }
  int operator--() {
    if(--index < 0) return 0;
    return 1;
  }
  int operator--(int) { return operator--(); }
  operator int() {
    return index >= 0 && index < ts.next;
  }
  Type* operator->() {
    Type* t = ts.storage[index];
    if(t) return t;
    require(0,"TStashIter::operator->return 0");
    return 0; // To allow inlining
  }
  // Remove the current element:
  int remove(Owns d = Default){
    return ts.remove(index, d);
  }
};

template<class Type, int sz>
TStash<Type, sz>::TStash(Owns owns) : _owns(owns) {
  quantity = 0;
  storage = 0;
  next = 0;
}

// Destruction of contained objects:
template<class Type, int sz>
TStash<Type, sz>::~TStash() {
  if(!storage) return;
  if(_owns == yes)
    for(int i = 0; i < count(); i++)
      delete storage[i];
  free(storage);
}

template<class Type, int sz>
int TStash<Type, sz>::add(Type* element) {
  if(next >= quantity)
    inflate();
  storage[next++] = element;
  return(next - 1); // Index number
}

template<class Type, int sz>
int TStash<Type, sz>::remove(int index, Owns d){
  if(index >= next || index < 0)
    return 0;
  switch(d) {
    case Default:
      if(_owns != yes) break;
    case yes:
      delete storage[index];
    case no:
      storage[index] = 0; // Position is empty
  }
  return 1;
}

template<class Type, int sz> inline
Type* TStash<Type, sz>::operator[](int index) {
  // Remove check for shipping application:
  require(index >= 0 && index < next);
  return storage[index];
}

template<class Type, int sz>
void TStash<Type, sz>::inflate(int increase) {
  void* v =
    realloc(storage, (quantity+increase)*sizeof(Type*));
  require(v != 0);  // Was it successful?
  storage = (Type**)v;
  quantity += increase;
}

#endif // TSTASH_H ///:~

The enum owns is global, although you’d normally want to nest it inside the class. Here it’s more convenient to use, but you can try moving it if you want to see the effect.

The storage pointer is made protected so inherited classes can directly access it. This means that the inherited classes may become dependent on the specific implementation of TStash, but as you’ll see in the Sorted.cpp example, it’s worth it.

The own flag indicates whether the container defaults to owning its objects. If so, in the destructor each object whose pointer is in the container is destroyed. This is straightforward; the container knows the type it contains. You can also change the default ownership in the constructor or read and modify it with the overloaded owns( ) function.

You should be aware that if the container holds pointers to a base-class type, that type should have a virtual destructor to ensure proper cleanup of derived objects whose addresses have been upcast when placing them in the container.

The TStashIter follows the iterator model of bonding to a single container object for its lifetime. In addition, the copy-constructor allows you to make a new iterator pointing at the same location as the existing iterator you create it from, effectively making a bookmark into the container. The forward( ) and backward( ) member functions allow you to jump an iterator by a number of spots, respecting the boundaries of the container. The overloaded increment and decrement operators move the iterator by one place. The smart pointer is used to operate on the element the iterator is referring to, and remove( ) destroys the current object by calling the container’s remove( ).

The following example creates and tests two different kinds of Stash objects, one for a new class called Int that announces its construction and destruction and one that holds objects of the class String from Chapter XX.

//: C16:TStashTest.cpp
// Test TStash
#include "TStash.h"
#include "../require.h"
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ofstream out("tstest.out");

class Int {
  int i;
public:
  Int(int ii = 0) : i(ii) {
    out << ">" << i << endl;
  }
  ~Int() { out << "~" << i << endl; }
  operator int() const { return i; }
  friend ostream&
    operator<<(ostream& os, const Int& x) {
      return os << x.i;
  }
};

int main() {
  TStash<Int> intStash; // Instantiate for Int
  for(int i = 0; i < 30; i++)
    intStash.add(new Int(i));
  TStashIter<Int> intIter(intStash);
  intIter.forward(5);
  for(int j = 0; j < 20; j++, intIter++)
    intIter.remove(); // Default removal
  for(int k = 0; k < intStash.count(); k++)
    if(intStash[k]) // Remove() causes "holes"
      out << *intStash[k] << endl;

  ifstream file("TStashTest.cpp");
  assure(file, "TStashTest.cpp");
  // Instantiate for String:
  TStash<string> stringStash;
  string line;
  while(getline(file, line))
    stringStash.add(new string(line));
  for(int u = 0; u < stringStash.count(); u++)
    if(stringStash[u])
      out << *stringStash[u] << endl;
  TStashIter<string> it(stringStash);
  int n = 25;
  it.forward(n);
  while(it) {
    out << n++ << ": " << it->c_str() << endl;
    it++;
  }

} ///:~

In both cases an iterator is created and used to move through the container. Notice the elegance produced by using these constructs: You aren’t assailed with the implementation details of using an array. You tell the container and iterator objects what to do, not how. This makes the solution easier to conceptualize, to build, and to modify.

stack as a template

The Stack class, last seen in Chapter XX, is also a container and is also best expressed as a template with an associated iterator. Here’s the new header file:

//: C16:TStack.h
// Stack using templates
#ifndef TSTACK_H
#define TSTACK_H

// Declaration required:
template<class T> class TStackIterator;

template<class T> class TStack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt) {
      data = dat;
      next = nxt;
    }
  }* head;
  int _owns;
public:
  TStack(int own = 1) : head(0), _owns(own) {}
  ~TStack();
  void push(T* dat) {
    head = new Link(dat,head);
  }
  T* peek() const { return head->data; }
  T* pop();
  int owns() const { return _owns; }
  void owns(int newownership) {
    _owns = newownership;
  }
  friend class TStackIterator<T>;
};

template<class T> T* TStack<T>::pop() {
  if(head == 0) return 0;
  T* result = head->data;
  Link* oldHead = head;
  head = head->next;
  delete oldHead;
  return result;
}

template<class T> TStack<T>::~TStack() {
  Link* cursor = head;
  while(head) {
    cursor = cursor->next;
    // Conditional cleanup of data:
    if(_owns) delete head->data;
    delete head;
    head = cursor;
  }
}

template<class T> class TStackIterator {
  TStack<T>::Link* p;
public:
  TStackIterator(const TStack<T>& tl)
    : p(tl.head) {}
  TStackIterator(const TStackIterator& tl)
    : p(tl.p) {}
  // operator++ returns boolean indicating end:
  int operator++() {
    if(p->next)
      p = p->next;
    else p = 0; // Indicates end of list
    return int(p);
  }
  int operator++(int) { return operator++(); }
  // Smart pointer:
  T* operator->() const {
    if(!p) return 0;
    return p->data;
  }
  T* current() const {
    if(!p) return 0;
    return p->data;
  }
  // int conversion for conditional test:
  operator int() const { return p ? 1 : 0; }
};

#endif // TSTACK_H ///:~

You’ll also notice the class has been changed to support ownership, which works now because the class knows the exact type (or at least the base type, which will work assuming virtual destructors are used). As with TStash, the default is for the container to destroy its objects but you can change this by either modifying the constructor argument or using the owns( ) read/write member functions.

The iterator is very simple and very small – the size of a single pointer. When you create a TStackIterator, it’s initialized to the head of the linked list, and you can only increment it forward through the list. If you want to start over at the beginning, you create a new iterator, and if you want to remember a spot in the list, you create a new iterator from the existing iterator pointing at that spot (using the copy-constructor).

To call functions for the object referred to by the iterator, you can use the smart pointer (a very common sight in iterators) or a function called current( ) that looks identical to the smart pointer because it returns a pointer to the current object, but is different because the smart pointer performs the extra levels of dereferencing (see Chapter XX). Finally, the operator int indicates whether or not you are at the end of the list and allows the iterator to be used in conditional statements.

The entire implementation is contained in the header file, so there’s no separate cpp file. Here’s a small test that also exercises the iterator:

//: C16:TStackTest.cpp
// Use template list & iterator
#include "TStack.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  ifstream file("TStackTest.cpp");
  assure(file, "TStackTest.cpp");
  TStack<string> textlines;
  // Read file and store lines in the list:
  string line;
  while(getline(file, line))
    textlines.push(new string(line));
  int i = 0;
  // Use iterator to print lines from the list:
  TStackIterator<string> it(textlines);
  TStackIterator<string>* it2 = 0;
  while(it) {
    cout << *it.current() << endl;
    it++;
    if(++i == 10) // Remember 10th line
      it2 = new TStackIterator<string>(it);
  }
  cout << *(it2->current()) << endl;
  delete it2;

} ///:~

A TStack is instantiated to hold String objects and filled with lines from a file. Then an iterator is created and used to move through the linked list. The tenth line is remembered by copy-constructing a second iterator from the first; later this line is printed and the iterator – created dynamically – is destroyed. Here, dynamic object creation is used to control the lifetime of the object.

This is very similar to earlier test examples for the Stack class, but now the contained objects are properly destroyed when the TStack is destroyed.

Contents | Prev | Next

Stash and stack as templates

The ownership problem

Stash as a template

stack as a template

Stash and stack
as templates