CodeGuru : Thinking in C++

Containers & iterators

Suppose you want to create a stack. In C, you would make a data structure and associated functions, but of course in C++ you package the two together into an abstract data type. This stack class will hold ints, to keep it simple:

//: C16:IStack.cpp
// Simple integer stack
#include "../require.h"
#include <iostream>
using namespace std;

class IStack {
  static const int ssize = 100;
  int stack[ssize];
  int top;
public:
  IStack() : top(0) { stack[top] = 0; }
  void push(int i) {
    if(top < ssize) stack[top++] = i;
  }
  int pop() {
    return stack[top > 0 ? --top : top];
  }
  friend class IStackIter;
};

// An iterator is a "super-pointer":
class IStackIter {
  IStack& S;
  int index;
public:
  IStackIter(IStack& is)
    : S(is), index(0) {}
  int operator++() { // Prefix form
    if (index < S.top - 1) index++;
    return S.stack[index];
  }
  int operator++(int) { // Postfix form
    int returnval = S.stack[index];
    if (index < S.top - 1) index++;
    return returnval;
  }
};
// For interest, generate Fibonacci numbers:
int fibonacci(int n) {
  const int sz = 100;
  require(n < sz);
  static int f[sz]; // Initialized to zero
  f[0] = f[1] = 1;
  // Scan for unfilled array elements:
  int i;
  for(i = 0; i < sz; i++)
    if(f[i] == 0) break;
  while(i <= n) {
    f[i] = f[i-1] + f[i-2];
    i++;
  }
  return f[n];
}

int main() {
  IStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Traverse with an iterator:
  IStackIter it(is);
  for(int j = 0; j < 20; j++)
    cout << it++ << endl;
  for(int k = 0; k < 20; k++)
    cout << is.pop() << endl;

} ///:~

The class IStack is an almost trivial example of a push-down stack. For simplicity it has been created here with a fixed size, but you can also modify it to automatically expand by allocating memory off the heap. (This will be demonstrated in later examples.)

The second class, IStackIter, is an example of an iterator, which you can think of as a superpointer that has been customized to work only with an IStack. Notice that IStackIter is a friend of IStack, which gives it access to all the private elements of IStack.

Like a pointer, IStackIter’s job is to move through an IStack and retrieve values. In this simple example, the IStackIter can move only forward (using both the pre- and postfix forms of the operator++) and it can fetch only values. However, there is no boundary to the way an iterator can be defined. It is perfectly acceptable for an iterator to move around any way within its associated container and to cause the contained values to be modified. However, it is customary that an iterator is created with a constructor that attaches it to a single container object and that it is not reattached during its lifetime. (Most iterators are small, so you can easily make another one.)

To make the example more interesting, the fibonacci( ) function generates the traditional rabbit-reproduction numbers. This is a fairly efficient implementation, because it never generates the numbers more than once. (Although if you’ve been out of school awhile, you’ve probably figured out that you don’t spend your days researching more efficient implementations of algorithms, as textbooks might lead you to believe.)

In main( ) you can see the creation and use of the stack and its associated iterator. Once you have the classes built, they’re quite simple to use.

The need for containers

Obviously an integer stack isn’t a crucial tool. The real need for containers comes when you start making objects on the heap using new and destroying them with delete. In the general programming problem, you don’t know how many objects you’re going to need while you’re writing the program. For example, in an air-traffic control system you don’t want to limit the number of planes your system can handle. You don’t want the program to abort just because you exceed some number. In a computer-aided design system, you’re dealing with lots of shapes, but only the user determines (at runtime) exactly how many shapes you’re going to need. Once you notice this tendency, you’ll discover lots of examples in your own programming situations.

C programmers who rely on virtual memory to handle their “memory management” often find the idea of new, delete, and container classes disturbing. Apparently, one practice in C is to create a huge global array, larger than anything the program would appear to need. This may not require much thought (or awareness of malloc( ) and free( )), but it produces programs that don’t port well and can hide subtle bugs.

In addition, if you create a huge global array of objects in C++, the constructor and destructor overhead can slow things down significantly. The C++ approach works much better: When you need an object, create it with new, and put its pointer in a container. Later on, fish it out and do something to it. This way, you create only the objects you absolutely need. And generally you don’t have all the initialization conditions at the start-up of the program; you have to wait until something happens in the environment before you can actually create the object.

So in the most common situation, you’ll create a container that holds pointers to some objects of interest. You will create those objects using new and put the resulting pointer in the container (potentially upcasting it in the process), fishing it out later when you want to do something with the object. This technique produces the most flexible, general sort of program.

Contents | Prev | Next

Contact: webmaster@codeguru.com
CodeGuru - the website for developers. [an error occurred while processing this directive]