Containers
Suppose you want to create a
stack, as we have been doing throughout the book. This
stack class will hold ints, to keep it simple:
//: C16:IntStack.cpp
// Simple integer stack
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;
class IntStack {
enum { ssize = 100 };
int stack[ssize];
int top;
public:
IntStack() : top(0) {}
void push(int i) {
require(top < ssize, "Too many push()es");
stack[top++] = i;
}
int pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
};
int main() {
IntStack is;
// Add some Fibonacci numbers, for interest:
for(int i = 0; i < 20; i++)
is.push(fibonacci(i));
// Pop & print them:
for(int k = 0; k < 20; k++)
cout << is.pop() << endl;
} ///:~
The class IntStack is a 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, as in the Stack class that has been examined
throughout the book.
main( ) adds some integers to
the stack, and pops them off again. To make the example more interesting, the
integers are created with the fibonacci( )
function, which generates the traditional rabbit-reproduction numbers. Here is
the header file that declares the function:
//: C16:fibonacci.h
// Fibonacci number generator
int fibonacci(int n); ///:~
Here’s the
implementation:
//: C16:fibonacci.cpp {O}
#include "../require.h"
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];
} ///:~
This is a fairly efficient
implementation, because it never generates the numbers more than once. It uses a
static array of
int, and relies on the fact that the compiler will initialize a
static array to zero. The first for loop moves the index i
to where the first array element is zero, then a while loop adds
Fibonacci numbers to the array until the desired element is reached. But notice
that if the Fibonacci numbers through element n are already initialized,
it skips the while loop
altogether.
