On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

Thinking in C++
Prev Contents / Index Next

## 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.

Thinking in C++
Prev Contents / Index Next

 Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire